{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Falling Path Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minFallingPathSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #下降路径最小和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>n x n</code> 的<strong> 方形 </strong>整数数组&nbsp;<code>matrix</code> ，请你找出并返回通过 <code>matrix</code> 的<strong>下降路径</strong><em> </em>的<strong> </strong><strong>最小和</strong> 。</p>\n",
    "\n",
    "<p><strong>下降路径</strong> 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 <code>(row, col)</code> 的下一个元素应当是 <code>(row + 1, col - 1)</code>、<code>(row + 1, col)</code> 或者 <code>(row + 1, col + 1)</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/11/03/failing1-grid.jpg\" style=\"height: 500px; width: 499px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[2,1,3],[6,5,4],[7,8,9]]\n",
    "<strong>输出：</strong>13\n",
    "<strong>解释：</strong>如图所示，为和最小的两条下降路径\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/11/03/failing2-grid.jpg\" style=\"height: 365px; width: 164px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[-19,57],[-40,-5]]\n",
    "<strong>输出：</strong>-59\n",
    "<strong>解释：</strong>如图所示，为和最小的下降路径\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == matrix.length == matrix[i].length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>-100 &lt;= matrix[i][j] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-falling-path-sum](https://leetcode.cn/problems/minimum-falling-path-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-falling-path-sum](https://leetcode.cn/problems/minimum-falling-path-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,1,3],[6,5,4],[7,8,9]]', '[[-19,57],[-40,-5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        for i in range(len(grid)):\n",
    "            for t in range(len(grid)):\n",
    "                grid[i][t] = [grid[i][t], t]\n",
    "            grid[i] = sorted(grid[i], key=lambda x:x[0])[:3]\n",
    "        for i in range(1, len(grid)):\n",
    "            for j in range(3):\n",
    "                tmp_min =sorted(grid[i-1], key=lambda x:x[0])[-1][0] + 1\n",
    "                for t in range(3):\n",
    "                    if grid[i-1][t][1] != grid[i][j][1] and grid[i-1][t][0] <= tmp_min:\n",
    "                        tmp_min = grid[i-1][t][0]\n",
    "                grid[i][j][0] += tmp_min\n",
    "        for i in grid:\n",
    "            print(i)\n",
    "        return sorted(grid[-1], key = lambda x:x[0])[0][0]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        '''\n",
    "        n = len(grid)\n",
    "        dp = [[float('inf') for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == 0:\n",
    "                    dp[i][j] = grid[i][j]\n",
    "                else:\n",
    "                    for k in range(n):\n",
    "                        if k != j:\n",
    "                            dp[i][j] = min(dp[i - 1][k] + grid[i][j], dp[i][j])\n",
    "        return min(dp[-1])\n",
    "        '''\n",
    "        j1 = j2 = float(-inf)\n",
    "        n = len(grid)\n",
    "        dp = [[float('inf') for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            tj1 = tj2 = float(-inf)\n",
    "            for j in range(n):\n",
    "                if i == 0:\n",
    "                    dp[i][j] = grid[i][j]\n",
    "                else:\n",
    "                    if j == j1:\n",
    "                        dp[i][j] = dp[i - 1][j2] + grid[i][j]\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i - 1][j1] + grid[i][j]\n",
    "                if tj1 < 0 or dp[i][j] < dp[i][tj1]:\n",
    "                    tj2, tj1 = tj1, j\n",
    "                elif tj2 < 0 or dp[i][j] < dp[i][tj2]:\n",
    "                    tj2 = j\n",
    "            j1 = tj1\n",
    "            j2 = tj2\n",
    "            # print(j1, j2, dp)\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        for i in range(1, n):\n",
    "            for j in range(n):\n",
    "                grid[i][j] = min([grid[i - 1][x] for x, y in enumerate(grid[i - 1]) if x != j]) + grid[i][j]\n",
    "        # print(grid)\n",
    "        return min(grid[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        for i in range(len(grid)):\n",
    "            for t in range(len(grid)):\n",
    "                grid[i][t] = [grid[i][t], t]\n",
    "            grid[i] = sorted(grid[i], key=lambda x:x[0])[:3]\n",
    "        for i in range(1, len(grid)):\n",
    "            for j in range(3):\n",
    "                tmp_min =sorted(grid[i-1], key=lambda x:x[0])[-1][0] + 1\n",
    "                for t in range(3):\n",
    "                    if grid[i-1][t][1] != grid[i][j][1] and grid[i-1][t][0] <= tmp_min:\n",
    "                        tmp_min = grid[i-1][t][0]\n",
    "                grid[i][j][0] += tmp_min\n",
    "        return sorted(grid[-1], key = lambda x:x[0])[0][0]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        M, N = len(grid), len(grid[0])\n",
    "        dp = [[0] * N for _ in range(M)]\n",
    "        x0 = y0 = -1\n",
    "        for i in range(M):\n",
    "            x1 = y1 = -1\n",
    "            for j in range(N):\n",
    "                if i == 0:\n",
    "                    dp[i][j] = grid[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = grid[i][j] + (dp[i - 1][x0] if j != x0 else dp[i - 1][y0])\n",
    "                if x1 == -1 or dp[i][j] < dp[i][x1]:\n",
    "                    x1, y1 = j, x1\n",
    "                elif y1 == -1 or dp[i][j] < dp[i][y1]:\n",
    "                    y1 = j\n",
    "            x0, y0 = x1, y1\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        for i in range(len(grid)):\n",
    "            for t in range(len(grid)):\n",
    "                grid[i][t] = [grid[i][t], t]\n",
    "            grid[i] = sorted(grid[i], key=lambda x:x[0])[:3]\n",
    "        for i in range(1, len(grid)):\n",
    "            for j in range(3):\n",
    "                tmp_min =sorted(grid[i-1], key=lambda x:x[0])[-1][0] + 1\n",
    "                for t in range(3):\n",
    "                    if grid[i-1][t][1] != grid[i][j][1] and grid[i-1][t][0] <= tmp_min:\n",
    "                        tmp_min = grid[i-1][t][0]\n",
    "                grid[i][j][0] += tmp_min\n",
    "        return sorted(grid[-1], key = lambda x:x[0])[0][0]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        ans=[]\n",
    "        ans.append([])\n",
    "        for i in range(n):\n",
    "            ans[-1].append(grid[0][i])\n",
    "        for row in range(1,m):\n",
    "            e=[]\n",
    "            for col in range(n):\n",
    "                if col==0:\n",
    "                    e.append(min(ans[-1][1:])+grid[row][col])\n",
    "                elif col<n-1:\n",
    "                    g=ans[-1][:col]+ans[-1][col+1:]\n",
    "                    e.append(min(g)+grid[row][col])\n",
    "                elif col==n-1:\n",
    "                    e.append(min(ans[-1][:col])+grid[row][col])\n",
    "            ans.append(e)\n",
    "        return min(ans[-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/u/l00/\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        yLen, xLen = len(grid), len(grid[0])\n",
    "        if xLen == 1: return grid[0][0]\n",
    "        dps = [0] * xLen\n",
    "        for row in grid:\n",
    "            leftMin = [1_000_000_007]\n",
    "            for i,num in enumerate(row):\n",
    "                row[i] = dps[i] + num\n",
    "                leftMin.append(min(leftMin[i], row[i]))\n",
    "            rightMin = row[-1]\n",
    "            row[-1] = leftMin[-2]\n",
    "            for i in range(xLen - 2, -1, -1):\n",
    "                num = row[i]\n",
    "                row[i] = min(rightMin, leftMin[i])\n",
    "                rightMin = min(rightMin, num)\n",
    "            dps = row\n",
    "        return min(dps)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        res_list = grid[0]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            new_res_list = [0] * n\n",
    "            for index, val in enumerate(grid[i]):\n",
    "                tmp = res_list[0:index]\n",
    "                tmp.extend(res_list[index + 1:])\n",
    "                new_res_list[index] = val + min(tmp)\n",
    "            res_list = new_res_list\n",
    "\n",
    "        return min(res_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        n = len(grid)\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(n):\n",
    "                grid[i][j] += min(grid[i + 1][:j] + grid[i + 1][j + 1:])\n",
    "\n",
    "        return min(grid[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "    n, prevMinFirstSum, prevMinFirstIndex, prevMinSecondSum = len(grid), 0, -1, 0\n",
    "    for i in range(0, n):\n",
    "      curMinFirstSum, curMinFirstIndex, curMinSecondSum = sys.maxsize, -1, sys.maxsize\n",
    "      for j in range(0, n):\n",
    "        curSum = prevMinSecondSum if j == prevMinFirstIndex else prevMinFirstSum\n",
    "        curSum += grid[i][j]\n",
    "        if curSum < curMinFirstSum:\n",
    "          curMinSecondSum = curMinFirstSum\n",
    "          curMinFirstSum = curSum\n",
    "          curMinFirstIndex = j\n",
    "        elif curSum < curMinSecondSum:\n",
    "          curMinSecondSum = curSum\n",
    "      prevMinFirstSum, prevMinSecondSum, prevMinFirstIndex = curMinFirstSum, curMinSecondSum, curMinFirstIndex\n",
    "    return prevMinFirstSum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        rows = len(grid)\n",
    "        min_idx = [row.index(min(row)) for row in grid]\n",
    "        min_idx_idx = [0 for i in range(rows)]\n",
    "        row = 0\n",
    "        while row < rows:\n",
    "            if row!= 0 and min_idx[row] == min_idx[row-1]:\n",
    "                tmp1 = grid[row][:]\n",
    "                tmp2 = grid[row-1][:]\n",
    "                tmp1.sort()\n",
    "                tmp2.sort()\n",
    "                if tmp1[0]-tmp1[1] < tmp2[0]-tmp2[1]:\n",
    "                    min_idx_idx[row-1] += 1\n",
    "                    min_idx[row-1] = grid[row-1].index(tmp2[min_idx_idx[row-1]])\n",
    "                else:\n",
    "                    min_idx_idx[row] += 1\n",
    "                    min_idx[row] = grid[row].index(tmp1[min_idx_idx[row]])\n",
    "            row += 1\n",
    "        ans = sum(grid[row][min_idx[row]] for row in range(rows))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        dp = grid[0][:]\n",
    "        n = len(grid)\n",
    "        for i in range(1, n):\n",
    "            # 保留 最小值和第二小\n",
    "            firstmin = secondmin = inf\n",
    "            for num in dp:\n",
    "                if num <= firstmin:\n",
    "                    secondmin = firstmin\n",
    "                    firstmin = num\n",
    "                elif num <= secondmin:\n",
    "                    secondmin = num\n",
    "            if secondmin == inf:  # 只有一个元素的情况\n",
    "                secondmin = 0\n",
    "            for _ in range(n):\n",
    "                if dp[_] > firstmin:\n",
    "                    dp[_] = firstmin\n",
    "                elif dp[_] == firstmin:\n",
    "                    dp[_] = secondmin\n",
    "            for j in range(n):\n",
    "                dp[j] = grid[i][j] + dp[j]\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        first_min_sum ,second_min_sum = 0,0 \n",
    "        first_min_index = -1 \n",
    "        for i in range(len(grid)):\n",
    "            cur_first_min_sum,cur_second_min_sum = 10**9,10**9\n",
    "            cur_first_min_index = -1 \n",
    "            for j in range(len(grid)):\n",
    "                cur_sum = grid[i][j]\n",
    "                if j != first_min_index:\n",
    "                    cur_sum += first_min_sum\n",
    "                else:\n",
    "                    cur_sum += second_min_sum\n",
    "                \n",
    "                if cur_sum < cur_first_min_sum:\n",
    "                    cur_second_min_sum,cur_first_min_sum = cur_first_min_sum,cur_sum\n",
    "                    cur_first_min_index = j\n",
    "                elif cur_sum < cur_second_min_sum:\n",
    "                    cur_second_min_sum = cur_sum \n",
    "            \n",
    "            first_min_sum,second_min_sum = cur_first_min_sum,cur_second_min_sum\n",
    "            first_min_index = cur_first_min_index\n",
    "        \n",
    "        return first_min_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        a = grid[0][:]\n",
    "        n = len(grid)\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            # 找到a中的最小值和次小值\n",
    "            min_val = float('inf')\n",
    "            second_min_val = float('inf')\n",
    "            for val in a:\n",
    "                if val <= min_val:\n",
    "                    second_min_val = min_val\n",
    "                    min_val = val\n",
    "                elif val < second_min_val:\n",
    "                    second_min_val = val\n",
    "            \n",
    "            b = []\n",
    "            for j in range(n):\n",
    "                # 如果当前列的值是上一行的最小值，则使用上一行的次小值进行计算\n",
    "                # 否则使用上一行的最小值进行计算\n",
    "                if a[j] == min_val:\n",
    "                    b.append(grid[i][j] + second_min_val)\n",
    "                else:\n",
    "                    b.append(grid[i][j] + min_val)\n",
    "            \n",
    "            a = b\n",
    "            \n",
    "        return min(a)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        dp = grid[0]\n",
    "        n = len(grid)\n",
    "        if n==1:\n",
    "            return grid[0][0]\n",
    "        for i in range(1, n):\n",
    "            mi, mic, ind, sec = inf, 0, -1, inf\n",
    "            for j in range(n):\n",
    "                if dp[j]<mi:\n",
    "                    sec = mi\n",
    "                    mi, mic, ind = dp[j], 1, j\n",
    "                elif dp[j]==mi:\n",
    "                    mic += 1\n",
    "                elif dp[j] < sec:\n",
    "                    sec = dp[j]\n",
    "            dp = [grid[i][j]+mi for j in range(n)]\n",
    "            if mic == 1:\n",
    "                dp[ind] += sec - mi\n",
    "        return min(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        distance = [num for num in grid[0]]\n",
    "        n = len(grid)\n",
    "        for i in range(1,n):\n",
    "            temp = [num for num in grid[i]]\n",
    "            for j in range(n):\n",
    "                min_val = 200000\n",
    "                for k in range(n):\n",
    "                    if k!=j:\n",
    "                        min_val = min(min_val,distance[k])\n",
    "                temp[j] += min_val \n",
    "            distance = [num for num in temp]\n",
    "        return min(distance)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        rows = len(grid)\n",
    "        min_idx = [row.index(min(row)) for row in grid]\n",
    "        min_idx_idx = [0 for i in range(rows)]\n",
    "        row = 0\n",
    "        while row < rows:\n",
    "            if row!= 0 and min_idx[row] == min_idx[row-1]:\n",
    "                tmp1 = grid[row][:]\n",
    "                tmp2 = grid[row-1][:]\n",
    "                tmp1.sort()\n",
    "                tmp2.sort()\n",
    "                if tmp1[0]-tmp1[1] < tmp2[0]-tmp2[1]:\n",
    "                    min_idx_idx[row-1] += 1\n",
    "                    min_idx[row-1] = grid[row-1].index(tmp2[min_idx_idx[row-1]])\n",
    "                else:\n",
    "                    min_idx_idx[row] += 1\n",
    "                    min_idx[row] = grid[row].index(tmp1[min_idx_idx[row]])\n",
    "            row += 1\n",
    "        ans = sum(grid[row][min_idx[row]] for row in range(rows))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        dp = grid[0].copy()\n",
    "        for l in grid[1:]:\n",
    "            mn, mn2 = nsmallest(2, dp)\n",
    "            for j, x in enumerate(l):\n",
    "                dp[j] = x + (mn if dp[j] != mn else mn2)\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        min_list = [0] * 2\n",
    "        columns = len(grid[0])\n",
    "        for element in grid:\n",
    "            getFirstAndSecondMin(min_list, columns, grid, element)\n",
    "        return min_list[0]\n",
    "        \n",
    "def getFirstAndSecondMin(min_list, columns, grid, element):\n",
    "    first_min, second_min = 20000, 20000\n",
    "    for column in range(columns):\n",
    "        if min_list[0] == grid[0][column]:\n",
    "            grid[0][column] = min_list[1] + element[column]\n",
    "        else:\n",
    "            grid[0][column] = min_list[0] + element[column]\n",
    "        if grid[0][column] < first_min:\n",
    "            second_min = first_min\n",
    "            first_min = grid[0][column]\n",
    "        elif grid[0][column] < second_min:\n",
    "            second_min = grid[0][column]\n",
    "    min_list[0], min_list[1] = first_min, second_min\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        first_min_sum = 0\n",
    "        second_min_sum = 0\n",
    "        first_min_index = -1 \n",
    "\n",
    "        for i in range(n):\n",
    "            cur_first_min, cur_second_min = 10**9, 10**9\n",
    "            cur_min_index = -1\n",
    "\n",
    "            for j in range(n):\n",
    "                cur_sum = matrix[i][j]\n",
    "                if j == first_min_index:\n",
    "                    cur_sum += second_min_sum\n",
    "                else:\n",
    "                    cur_sum += first_min_sum\n",
    "                if cur_sum < cur_first_min:\n",
    "                    cur_second_min = cur_first_min\n",
    "                    cur_first_min = cur_sum\n",
    "                    cur_min_index = j\n",
    "                elif cur_sum < cur_second_min:\n",
    "                    cur_second_min = cur_sum\n",
    "            first_min_sum, second_min_sum = cur_first_min, cur_second_min\n",
    "            first_min_index = cur_min_index\n",
    "            \n",
    "        return first_min_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        first_min_sum, second_min_sum = 0, 0\n",
    "        first_min_index = -1\n",
    "        for i in range(len(grid)):\n",
    "            cur_first_min_sum, cur_second_min_sum = 10**9, 10**9\n",
    "            cur_first_min_index = -1\n",
    "            for j in range(len(grid)):\n",
    "                cur_sum = grid[i][j]\n",
    "                if j != first_min_index:\n",
    "                    cur_sum += first_min_sum\n",
    "                else:\n",
    "                    cur_sum += second_min_sum\n",
    "                if cur_sum < cur_first_min_sum:\n",
    "                    cur_second_min_sum, cur_first_min_sum = cur_first_min_sum, cur_sum\n",
    "                    cur_first_min_index = j\n",
    "                elif cur_sum < cur_second_min_sum:\n",
    "                    cur_second_min_sum = cur_sum\n",
    "            first_min_sum, second_min_sum = cur_first_min_sum, cur_second_min_sum\n",
    "            first_min_index = cur_first_min_index\n",
    "        return first_min_sum\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        first_min_sum = 0\n",
    "        second_min_sum = 0\n",
    "        first_min_index = -1 \n",
    "\n",
    "        for i in range(n):\n",
    "            cur_first_min, cur_second_min = 10**9, 10**9\n",
    "            cur_min_index = -1\n",
    "\n",
    "            for j in range(n):\n",
    "                cur_sum = matrix[i][j]\n",
    "                if j == first_min_index:\n",
    "                    cur_sum += second_min_sum\n",
    "                else:\n",
    "                    cur_sum += first_min_sum\n",
    "                if cur_sum < cur_first_min:\n",
    "                    cur_second_min = cur_first_min\n",
    "                    cur_first_min = cur_sum\n",
    "                    cur_min_index = j\n",
    "                elif cur_sum < cur_second_min:\n",
    "                    cur_second_min = cur_sum\n",
    "            first_min_sum, second_min_sum = cur_first_min, cur_second_min\n",
    "            first_min_index = cur_min_index\n",
    "            \n",
    "        return first_min_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        dp =grid[0]\n",
    "        for i in range(1, len(grid)):\n",
    "            dp = [grid[i][j]+min(dp[:j]+dp[j+1:]) for j in range(n)]\n",
    "        return min(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        def get_third_min( n_list: list[int]):\n",
    "            res = [ [0,inf] , [0,inf] , [0,inf]]\n",
    "            for idx,val in enumerate(n_list):\n",
    "                if val < res[0][1]:\n",
    "                    res[2] = res[1]\n",
    "                    res[1] = res[0]\n",
    "                    res[0] = [idx,val]\n",
    "                elif val < res[1][1]:\n",
    "                    res[2] = res[1]\n",
    "                    res[1] = [idx,val]\n",
    "                elif val < res[2][1]:\n",
    "                    res[2] = [idx,val]\n",
    "                else:\n",
    "                    continue\n",
    "            return res\n",
    "        dp = [ [-1,0],[-1,0] , [-1,0]]\n",
    "        for i in grid:\n",
    "            tmp_min = get_third_min(i)\n",
    "            print(tmp_min , dp)\n",
    "            tmp_dp = []\n",
    "            for cur in tmp_min:\n",
    "                tmp_routine = [cur[0] , inf ]   #到某点的最短路径\n",
    "                for tmp_prev in dp:\n",
    "                    if tmp_prev[0] == cur[0]:   #来自同一列，则跳过\n",
    "                        continue\n",
    "                    else:\n",
    "                        tmp_routine[1] = min( tmp_routine[1] , tmp_prev[1] + cur[1] )\n",
    "                tmp_dp.append(tmp_routine)\n",
    "            dp = tmp_dp\n",
    "        return min(dp[0][1] , dp[1][1] , dp[2][1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        dp = grid[0].copy()\n",
    "        n = len(dp)\n",
    "        for l in grid[1:]:\n",
    "            mn, mn2 = nsmallest(2, dp)\n",
    "            for j, x in enumerate(l):\n",
    "                dp[j] = x + (mn if dp[j] != mn else mn2)\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        # from answer, record the min_sum_value, min_sum_value_index, second_min_sum_value,\n",
    "        # then for next row, if idx == min_sum_value_index, then use second_min_sum_value + row[idx] else use min_sum_value + row[idx]\n",
    "\n",
    "        # dp[i][j] means in the i row, and select j's min value\n",
    "        # dp[i][j] = min(dp[i-1][0], dp[i-1][1],..., dp[i-1][j-1],dp[i-1][j+1],...,dp[i-1][n-1]) + grid[i][j]\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        dp1 = grid[0]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            dp2 = [0] * n\n",
    "            for j in range(n):\n",
    "                dp2[j] = min([] + dp1[0:j] + dp1[j+1:]) + grid[i][j]\n",
    "            dp1 = dp2\n",
    "\n",
    "        return min(dp1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        if m == 1:\n",
    "            return grid[0][0]\n",
    "        dp_pre = [0] * m\n",
    "        dp_cur = [0] * m\n",
    "        for i in range(m):\n",
    "            for j in range(m):\n",
    "                dp_cur[j] = min(dp_pre[0:j] + dp_pre[j+1:m]) + grid[i][j]\n",
    "            dp_pre = dp_cur.copy()\n",
    "        return min(dp_cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if n == 1:\n",
    "            return grid[0][0]\n",
    "        dp = grid[0].copy()\n",
    "        for i in range(1, n):\n",
    "            queue = PriorityQueue()\n",
    "            for j in range(n):\n",
    "                queue.put((dp[j], j))\n",
    "            m1value, m1index = queue.get()\n",
    "            m2value, m2index = queue.get()\n",
    "            for j in range(n):\n",
    "                dp[j] = grid[i][j] + (m2value if j == m1index else m1value)\n",
    "            print(grid[i], dp)\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if n==1:\n",
    "            return grid[0][0]\n",
    "        dp = [0] * n\n",
    "        for i in range(n):\n",
    "            next_dp = [0] * n\n",
    "            for j in range(n):\n",
    "                if j==0:\n",
    "                    next_dp[j] = min(dp[1:])\n",
    "                elif j==n-1:\n",
    "                    next_dp[j] = min(dp[:j])\n",
    "                else:\n",
    "                    next_dp[j] = min(min(dp[:j]),min(dp[j+1:]))\n",
    "                next_dp[j] += grid[i][j]\n",
    "            print(next_dp)\n",
    "            dp,next_dp = next_dp,dp\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        dp = [0 for i in range(len(grid))]\n",
    "        dp[0] = min(grid[0])\n",
    "        index1 = 0\n",
    "        index2 = 0\n",
    "        index3 = 100\n",
    "        index4 = 100\n",
    "        for i in range(1, len(grid)):\n",
    "            index1 = grid[i-1].index(min(grid[i-1]))\n",
    "            index2 = grid[i].index(min(grid[i]))\n",
    "            if (index1 != index2 or index1 == index3) and index2 != index4 :\n",
    "                dp[i] = dp[i-1] + min(grid[i])\n",
    "                if index1 == index3:\n",
    "                    index3 = index4\n",
    "                else:\n",
    "                    index3 = index1\n",
    "                index4 = index2\n",
    "            else:\n",
    "                before = sorted(grid[i-1])\n",
    "                after = sorted(grid[i])\n",
    "                if before[0] + after[1] > before[1] + after[0]:\n",
    "                    dp[i] = dp[i-1] - before[0] + before[1] + after[0]\n",
    "                    index3 = grid[i-1].index(before[1])\n",
    "                    index4 = grid[i].index(after[0])\n",
    "                else:\n",
    "                    dp[i] = dp[i-1] + after[1]\n",
    "                    index3 = index1\n",
    "                    index4 = grid[i].index(after[1])\n",
    "        print(dp)\n",
    "        return dp[len(grid) - 1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "\n",
    "        @cache\n",
    "        def dp(i):\n",
    "            if i == n - 1: \n",
    "                arr = list(zip(grid[i], range(m)))\n",
    "                hq.heapify(arr)\n",
    "\n",
    "                fir = hq.heappop(arr)\n",
    "                if len(arr) < 2:\n",
    "                    return fir, (inf, -1)\n",
    "                sec = hq.heappop(arr)\n",
    "                return fir, sec\n",
    "\n",
    "            res = []\n",
    "            fir, sec = dp(i + 1)\n",
    "            res = []\n",
    "            for t in range(m):\n",
    "                val = grid[i][t]\n",
    "                if t == fir[1]:\n",
    "                    hq.heappush(res, (sec[0] + val, t))\n",
    "                else:\n",
    "                    hq.heappush(res, (fir[0] + val, t))\n",
    "            \n",
    "            f = hq.heappop(res)\n",
    "            s = hq.heappop(res)\n",
    "            return f, s \n",
    "        \n",
    "        res = dp(0)\n",
    "        del dp\n",
    "        return res[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        if len(grid)==1:return min(grid[0])\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        grid[0]=[(grid[0][i],i) for i in range(len(grid[0]))]\n",
    "        heapq.heapify(grid[0])\n",
    "        min1=heapq.heappop(grid[0])\n",
    "        min2=heapq.heappop(grid[0])\n",
    "        for i in range(1,m):\n",
    "            dp=[0 for i in range(n)]\n",
    "            for j in range(n):\n",
    "                if min1[1]==j:\n",
    "                    dp[j]=(min2[0]+grid[i][j],j)\n",
    "                else:\n",
    "                    dp[j]=(min1[0]+grid[i][j],j)\n",
    "            heapq.heapify(dp)\n",
    "            min1=heapq.heappop(dp)\n",
    "            min2=heapq.heappop(dp)\n",
    "        return min1[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, arr: List[List[int]]) -> int:\n",
    "        if len(arr) == 1:\n",
    "            return arr[0][0]\n",
    "\n",
    "        dp = [[0]*len(arr), [0]*len(arr)]\n",
    "        for i in range(len(arr[0])):\n",
    "            dp[0][i] = arr[0][i]\n",
    "\n",
    "        f = 1\n",
    "        for i in range(1, len(arr)):\n",
    "            for j in range(len(arr)):\n",
    "                dp[f][j] = arr[i][j] + min(dp[f-1][:j]+dp[f-1][j+1:])\n",
    "            f = 0 if f == 1 else 1\n",
    "\n",
    "            print(dp)\n",
    "\n",
    "        return min(dp[f-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        H = len(grid)\n",
    "        W = len(grid[0])\n",
    "\n",
    "        if(H==1):\n",
    "            return grid[0][0]\n",
    "\n",
    "        \n",
    "        if(grid[0][0]>grid[0][1]):\n",
    "            minindex1 = 1\n",
    "            minindex2 = 0\n",
    "        else:\n",
    "            minindex1 = 0\n",
    "            minindex2 = 1\n",
    "        for i in range(2,W):\n",
    "            v = grid[0][i]\n",
    "            if v<grid[0][minindex1]:\n",
    "                minindex2 = minindex1\n",
    "                minindex1 = i\n",
    "            elif v<grid[0][minindex2]:\n",
    "                minindex2 = i\n",
    "        minv1 = grid[0][minindex1]\n",
    "        minv2 = grid[0][minindex2]\n",
    "\n",
    "        for i in range(1,H):\n",
    "\n",
    "            print(minv1, minv2, minindex1, minindex2)\n",
    "\n",
    "            v0 = grid[i][0]+minv1 if minindex1!=0 else grid[i][0]+minv2\n",
    "            v1 = grid[i][1]+minv1 if minindex1!=1 else grid[i][0]+minv2\n",
    "\n",
    "            if(v0>v1):\n",
    "                next_minindex1 = 1\n",
    "                next_minv1 = v1\n",
    "                next_minindex2 = 0\n",
    "                next_minv2 = v0\n",
    "            else:\n",
    "                next_minindex1 = 0\n",
    "                next_minv1 = v0\n",
    "                next_minindex2 = 1\n",
    "                next_minv2 = v1\n",
    "            for j in range(2,W):\n",
    "                v = grid[i][j]+minv1 if minindex1!=j else grid[i][j]+minv2\n",
    "                if v<next_minv1:\n",
    "                    next_minindex2 = next_minindex1\n",
    "                    next_minv2 = next_minv1\n",
    "                    next_minindex1 = j\n",
    "                    next_minv1 = v\n",
    "                elif v<next_minv2:\n",
    "                    next_minindex2 = j\n",
    "                    next_minv2 = v\n",
    "\n",
    "            minv1 = next_minv1\n",
    "            minv2 = next_minv2\n",
    "            minindex1 = next_minindex1\n",
    "            minindex2 = next_minindex2\n",
    "\n",
    "        \n",
    "        return minv1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: list[list[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[0][i] = matrix[0][i]\n",
    "        for i in range(1, n):\n",
    "            for j in range(n):\n",
    "                dp[i][j] = float(inf)\n",
    "                for k in range(n):\n",
    "                    if j!=k:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i - 1][k] + matrix[i][j])\n",
    "\n",
    "        print(dp)\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        if m == 1:\n",
    "            return grid[0][0]\n",
    "\n",
    "        min_mat = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            if i == 0:\n",
    "                base_list = grid[i]\n",
    "                left_min_list = [float('inf')] * n\n",
    "                right_min_list = [float('inf')] * n\n",
    "                min_list = [0] * n\n",
    "                for j in range(n):\n",
    "                    if j != 0:\n",
    "                        left_min_list[j] = min(base_list[j - 1], left_min_list[j - 1])\n",
    "                for j in range(n - 1, -1, -1):\n",
    "                    if j != n - 1:\n",
    "                        right_min_list[j] = min(base_list[j + 1], right_min_list[j + 1])\n",
    "                for j in range(n):\n",
    "                    min_mat[i][j] = min(left_min_list[j], right_min_list[j])\n",
    "            else:\n",
    "                base_list = [grid[i][j] + min_mat[i - 1][j] for j in range(n)]\n",
    "                left_min_list = [float('inf')] * n\n",
    "                right_min_list = [float('inf')] * n\n",
    "                min_list = [0] * n\n",
    "                for j in range(n):\n",
    "                    if j != 0:\n",
    "                        left_min_list[j] = min(base_list[j - 1], left_min_list[j - 1])\n",
    "                for j in range(n - 1, -1, -1):\n",
    "                    if j != n - 1:\n",
    "                        right_min_list[j] = min(base_list[j + 1], right_min_list[j + 1])\n",
    "                for j in range(n):\n",
    "                    min_mat[i][j] = min(left_min_list[j], right_min_list[j])\n",
    "        return min(min_mat[-1])\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        f = copy.deepcopy(grid)\n",
    "        # f = grid\n",
    "        n = len(f)\n",
    "        if n == 1:\n",
    "            return f[0][0]\n",
    "        for i in range(1,n):\n",
    "            i1,v1,v2 = 0,float('inf'),float('inf')\n",
    "            for j in range(n):\n",
    "                if f[i-1][j] < v1:\n",
    "                    v2 = v1\n",
    "                    v1 = f[i-1][j]\n",
    "                    i1 = j\n",
    "                elif v1 <= f[i-1][j] < v2:\n",
    "                    v2 = f[i-1][j]\n",
    "\n",
    "            for j in range(n):\n",
    "                if j == i1:\n",
    "                    f[i][j] += v2\n",
    "                else:\n",
    "                    f[i][j] += v1\n",
    "                # if j == 0:\n",
    "                #     f[i][j] += f[i-1][j+1]\n",
    "                # elif j == n-1:\n",
    "                #     f[i][j] += f[i-1][j-1]\n",
    "                # else:\n",
    "                #     f[i][j] += min(f[i-1][j-1],f[i-1][j+1])\n",
    "        return min(f[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        f = copy.deepcopy(grid)\n",
    "        # f = grid\n",
    "        n = len(f)\n",
    "        if n == 1:\n",
    "            return f[0][0]\n",
    "        for i in range(1,n):\n",
    "            i1,i2,v1,v2 = 0,0,float('inf'),float('inf')\n",
    "            for j in range(n):\n",
    "                if f[i-1][j] < v1:\n",
    "                    v2 = v1\n",
    "                    v1 = f[i-1][j]\n",
    "                    i1 = j\n",
    "                elif v1 <= f[i-1][j] < v2:\n",
    "                    v2 = f[i-1][j]\n",
    "\n",
    "            for j in range(n):\n",
    "                if j == i1:\n",
    "                    f[i][j] += v2\n",
    "                else:\n",
    "                    f[i][j] += v1\n",
    "                # if j == 0:\n",
    "                #     f[i][j] += f[i-1][j+1]\n",
    "                # elif j == n-1:\n",
    "                #     f[i][j] += f[i-1][j-1]\n",
    "                # else:\n",
    "                #     f[i][j] += min(f[i-1][j-1],f[i-1][j+1])\n",
    "        return min(f[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        l = len(grid)\n",
    "        dp = deepcopy(grid)\n",
    "        for i in range(l):\n",
    "            for j in range(l):\n",
    "                if i>0:\n",
    "                    line = dp[i-1][:]\n",
    "                    del line[j]\n",
    "                    dp[i][j] = grid[i][j] + min(line[:])\n",
    "                else:\n",
    "                    dp[i][j] = grid[i][j]\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[float(\"inf\")] * n for _ in range(m)]\n",
    "        dp[0] = grid[0]\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                for idx in range(n):\n",
    "                    if idx != j:\n",
    "                        dp[i][j] = min(dp[i-1][idx], dp[i][j])\n",
    "                dp[i][j] += grid[i][j]\n",
    "                # elif j < i:\n",
    "                #     dp[i%2][j] = dp[(i-1)%2][j]\n",
    "                # dp[i][j] += matrix[i][j]\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        d = [[10**9 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            d[0][i] = grid[0][i]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    if j == k:\n",
    "                        continue\n",
    "                    d[i][j] = min(d[i][j], d[i - 1][k] + grid[i][j])\n",
    "        return min(d[n - 1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        d = [[10**9 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            d[0][i] = grid[0][i]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    if j == k:\n",
    "                        continue\n",
    "                    d[i][j] = min(d[i][j], d[i - 1][k] + grid[i][j])\n",
    "        return min(d[n - 1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        if not grid:\n",
    "            return 0\n",
    "        if len(grid)==1:\n",
    "            return grid[0][0]\n",
    "        n=len(grid)\n",
    "        f=[[0]*n for i in range(n)]\n",
    "        f[0]=grid[0]\n",
    "        for i in range(1,n):\n",
    "            for j in range(n):\n",
    "                f[i][j]=min(f[i-1][:j]+f[i-1][j+1:])+grid[i][j]\n",
    "        return min(f[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        nums=grid\n",
    "        for j in range(n-1):\n",
    "            for i in range(n):\n",
    "                nums1=[0]*n\n",
    "                for k in range(n):\n",
    "                    nums1[k]=nums[n-1-j][k]\n",
    "                del nums1[i]\n",
    "                nums[n-2-j][i]=min(nums1)+nums[n-2-j][i]\n",
    "        return min(nums[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        dp = [[float('inf')] * n for _ in range(n)]\n",
    "        dp[0] = grid[0]\n",
    "        for i in range(1, n):\n",
    "            for j in range(n):\n",
    "                for k in range(n):  # 这一个表示选取上一行最小路径和的情况\n",
    "                    if k == j:  # 相邻的两行不能在同一列\n",
    "                        continue\n",
    "                    dp[i][j] = min(dp[i][j], dp[i-1][k] + grid[i][j])\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        for i in range(n):\n",
    "            dp[0][i] = grid[0][i]\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                dp[i][j] = grid[i][j] + self.find_min(dp[i-1], j)\n",
    "        return min(dp[-1])\n",
    "    \n",
    "    def find_min(self, array, idx):\n",
    "        min_val = float(\"inf\")\n",
    "        for i in range(len(array)):\n",
    "            if i == idx:\n",
    "                continue\n",
    "            min_val = min(min_val, array[i])\n",
    "        return min_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        s1 = s2 = 0\n",
    "        index = -1\n",
    "\n",
    "        for l in grid:\n",
    "            new_s1 = new_s2 = inf\n",
    "            new_index = 0\n",
    "            for i in range(n):\n",
    "                if i == index:\n",
    "                    l[i] += s2\n",
    "                else:\n",
    "                    l[i] += s1\n",
    "                if l[i] < new_s1:\n",
    "                    new_s2, new_s1 = new_s1, l[i]\n",
    "                    new_index = i\n",
    "                elif l[i] < new_s2:\n",
    "                    new_s2 = l[i]\n",
    "            s1, s2, index = new_s1, new_s2, new_index\n",
    "\n",
    "        return s1\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "def get_min_index(nums: List[int]) -> (int, int):\n",
    "    i1, i2 = None, None\n",
    "    for i in range(0, len(nums)):\n",
    "        if i == 0:\n",
    "            i1 = i\n",
    "        elif nums[i] <= nums[i1]:\n",
    "            i2 = i1\n",
    "            i1 = i\n",
    "        elif i2 is None or nums[i] <= nums[i2]:\n",
    "            i2 = i\n",
    "    return i1, i2\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        for i in range(0, len(grid)):\n",
    "            i1, i2 = get_min_index(grid[0 if i - 1 < 0 else i - 1])\n",
    "            if i == 0:\n",
    "                continue\n",
    "            for j in range(0, len(grid[i])):\n",
    "                if j == i1:\n",
    "                    grid[i][j] += grid[i - 1][i2]\n",
    "                else:\n",
    "                    grid[i][j] += grid[i - 1][i1]\n",
    "\n",
    "        return min(grid[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        for i in range(0, len(grid)):\n",
    "            for j in range(0, len(grid[i])):\n",
    "                if i == 0:\n",
    "                    continue\n",
    "                grid[i][j] += min(grid[i - 1][0:j] + grid[i - 1][j + 1:])\n",
    "        return min(grid[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        f =[[inf]*n for _ in range(n)]\n",
    "        for j in range(n):f[-1][j] = grid[-1][j]\n",
    "\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(n):\n",
    "\n",
    "                for nj in range(n):\n",
    "                    if nj != j:\n",
    "                        f[i][j] = min(f[i][j], f[i+1][nj] + grid[i][j])\n",
    "        return min([f[0][j] for j in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            dp[-1][j] = grid[-1][j]\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    minpath = min(dp[i + 1][j + 1:])\n",
    "                elif j == n - 1:\n",
    "                    minpath = min(dp[i + 1][:j])\n",
    "                else:\n",
    "                    minpath = min(min(dp[i + 1][j + 1:]), min(dp[i + 1][:j]))\n",
    "                dp[i][j] = grid[i][j] + minpath\n",
    "        return min(dp[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[0][i] = matrix[0][i]\n",
    "        for i in range(1, n):\n",
    "            for j in range(n):\n",
    "                val = float(\"inf\")\n",
    "                for k in range(n):\n",
    "                    if j == k:\n",
    "                        continue\n",
    "                    val = min(dp[i-1][k], val)\n",
    "                dp[i][j] = val + matrix[i][j]\n",
    "        \n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        f =[[inf]*n for _ in range(n)]\n",
    "        MIN1, MIN2 = [inf -1], [inf, -1]  # 最大 次大\n",
    "        for j in range(n):\n",
    "            cur = f[-1][j] = grid[-1][j]\n",
    "            if MIN1[0] > cur:\n",
    "                if MIN1[0] < MIN2[0]:\n",
    "                    MIN2 = MIN1\n",
    "                MIN1 = [cur, j]\n",
    "            elif MIN2[0] > cur:\n",
    "                MIN2 = [cur, j]\n",
    "\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(n):\n",
    "\n",
    "                if j != MIN1[1]:\n",
    "                    f[i][j] = min(f[i][j], MIN1[0] + grid[i][j])\n",
    "                else:\n",
    "                    f[i][j] = min(f[i][j], MIN2[0] + grid[i][j])\n",
    "\n",
    "            MIN1,MIN2 = [inf,-1],[inf,-1]\n",
    "\n",
    "            for j in range(n):\n",
    "                if MIN1[0] > f[i][j]:\n",
    "                    if MIN1[0] < MIN2[0]:\n",
    "                        MIN2 = MIN1\n",
    "                    MIN1 = [f[i][j], j]\n",
    "                elif MIN2[0] > f[i][j]:\n",
    "                    MIN2 = [f[i][j], j]\n",
    "        return min([f[0][j] for j in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        for i in range(1,len(grid)):\n",
    "            for j in range(len(grid[i])):\n",
    "                if j==0:\n",
    "                    grid[i][j]+=min(grid[i-1][1:len(grid[i])])\n",
    "                elif j==len(grid[i])-1:\n",
    "                    grid[i][j]+=min(grid[i-1][0:len(grid[i-1])-1])\n",
    "                else:\n",
    "                    grid[i][j]+=min(grid[i-1][0:j]+grid[i-1][j+1:len(grid[i])])\n",
    "        return min(grid[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "def get_min_index(nums: List[int]) -> (int, int):\n",
    "    i1, i2 = None, None\n",
    "    for i in range(0, len(nums)):\n",
    "        if i == 0:\n",
    "            i1 = i\n",
    "        elif nums[i] <= nums[i1]:\n",
    "            i2 = i1\n",
    "            i1 = i\n",
    "        elif i2 is None or nums[i] <= nums[i2]:\n",
    "            i2 = i\n",
    "    return i1, i2\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        for i in range(0, len(grid)):\n",
    "            i1, i2 = get_min_index(grid[0 if i - 1 < 0 else i - 1])\n",
    "            if i == 0:\n",
    "                continue\n",
    "            for j in range(0, len(grid[i])):\n",
    "                if j == i1:\n",
    "                    grid[i][j] += grid[i - 1][i2]\n",
    "                else:\n",
    "                    grid[i][j] += grid[i - 1][i1]\n",
    "\n",
    "        return min(grid[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        grid_len = len(grid)\n",
    "        if grid_len == 1:\n",
    "            return grid[0][0]\n",
    "        result_grid = [[0 for i in range(grid_len)] for j in range(grid_len)]\n",
    "        # val_col = [[100, 0], [100, 0]]\n",
    "        current_val_col = [[0, -1], [0, -1]]\n",
    "        for i in range(grid_len):\n",
    "            val_col = [[current_val_col[0][0]+100, current_val_col[0][1]], [current_val_col[1][0]+100, current_val_col[1][1]]]\n",
    "            for j in range(grid_len):\n",
    "                if current_val_col[0][1] != j:\n",
    "                    result_grid[i][j] = current_val_col[0][0] + grid[i][j]\n",
    "                else:\n",
    "                    result_grid[i][j] = current_val_col[1][0] + grid[i][j]\n",
    "                if result_grid[i][j] < val_col[0][0]:\n",
    "                    val_col = [[result_grid[i][j], j], val_col[0]]\n",
    "                elif result_grid[i][j] < val_col[1][0]:\n",
    "                    val_col[1] = [result_grid[i][j], j]\n",
    "            current_val_col = val_col\n",
    "\n",
    "        result_row = result_grid[-1]\n",
    "        res_ans = result_row[0]\n",
    "        for i in range(1, grid_len):\n",
    "            if result_row[i] < res_ans:\n",
    "                res_ans = result_row[i]\n",
    "        \n",
    "        return res_ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        # dp = [[0]*n for _ in range(n)]\n",
    "        # dp[0] = grid[0]\n",
    "        dp = copy.deepcopy(grid)\n",
    "        temp = [0]*n\n",
    "\n",
    "        if(n==1): return grid[0][0]\n",
    "        for i in range(1,n):\n",
    "            temp = copy.deepcopy(dp[i-1])\n",
    "            # temp = dp[i-1] \n",
    "            for j in range(n):\n",
    "                temp[j] = float(\"Inf\")\n",
    "                dp[i][j] = min(temp) + grid[i][j]\n",
    "                temp[j] = dp[i-1][j]\n",
    "                \n",
    "\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 回溯，超时\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        ans=float('inf')\n",
    "        s=0\n",
    "        def dfs(row,curCol):\n",
    "            nonlocal s, ans\n",
    "            s += grid[row][curCol]\n",
    "            if row==n-1:\n",
    "                ans=min(s,ans)\n",
    "                return\n",
    "            # 这里不能这样剪枝，因为grid[i][j]有可能是负数\n",
    "            # if s>ans:\n",
    "            #     return\n",
    "            for j in range(n):\n",
    "                if j!=curCol:\n",
    "                    dfs(row+1,j)\n",
    "                    s-=grid[row+1][j]\n",
    "        for i in range(n):\n",
    "            s=0\n",
    "            dfs(0,i)\n",
    "        return ans\n",
    "\n",
    "# dp\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        inf=float('inf')\n",
    "        dp=[[inf]*n for _ in range(n)]\n",
    "        for j in range(n):\n",
    "            dp[0][j]=grid[0][j]\n",
    "        for i in range(1,n):\n",
    "            for j in range(n):\n",
    "                # for k in range(n):\n",
    "                #     if k!=j:\n",
    "                #         dp[i][j]=min(dp[i-1][k]+grid[i][j],dp[i][j])\n",
    "                if j==0:\n",
    "                    m=min(dp[i-1][j+1:])\n",
    "                elif j==n-1:\n",
    "                    m=min(dp[i-1][0:j])\n",
    "                else:\n",
    "                    m=min(min(dp[i-1][0:j]),min(dp[i-1][j+1:]))\n",
    "                dp[i][j] = m+grid[i][j]\n",
    "        return min(dp[n-1])\n",
    "\n",
    "# 维护最小值和次小值\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        inf=float('inf')\n",
    "        dp=[[inf]*n for _ in range(n)]\n",
    "        first_small_index=0\n",
    "        first_small=0\n",
    "        second_small=0\n",
    "        for i in range(n):\n",
    "            fs, ss, fsi = 0, 0, 0\n",
    "            for j in range(n):\n",
    "                if j!=first_small_index:\n",
    "                    dp[i][j] = first_small + grid[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = second_small + grid[i][j]\n",
    "                if j == 0:\n",
    "                    fs = dp[i][j]\n",
    "                    fsi = 0\n",
    "                elif j == 1:\n",
    "                    ss = dp[i][j]\n",
    "                    if fs > ss:\n",
    "                        fs, ss = ss, fs\n",
    "                        fsi = 1\n",
    "                else:\n",
    "                    if dp[i][j] < fs:\n",
    "                        ss = fs\n",
    "                        fs=dp[i][j]\n",
    "                        fsi = j\n",
    "                    elif dp[i][j] < ss:\n",
    "                        ss = dp[i][j]\n",
    "\n",
    "            first_small=fs\n",
    "            second_small=ss\n",
    "            first_small_index=fsi\n",
    "        return min(dp[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "\n",
    "        def find_min_idx_2(arr):\n",
    "            nonlocal n\n",
    "            min_val = 10**9\n",
    "            min_idx = -1\n",
    "            for i in range(n):\n",
    "                if(arr[i] < min_val):\n",
    "                    min_val = arr[i]\n",
    "                    min_idx = i\n",
    "                \n",
    "            min2_val = 10**9\n",
    "            for i in range(n):\n",
    "                if(arr[i] < min2_val and i != min_idx):\n",
    "                    min2_val = arr[i]\n",
    "            \n",
    "            print(min_val, min_idx, min2_val)\n",
    "\n",
    "            return min_val, min_idx, min2_val\n",
    "\n",
    "\n",
    "        dp_grid = [[0] * n  for _ in range(n)]\n",
    "\n",
    "        dp_grid[0] = grid[0].copy()\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            min_val, min_idx, min2_val = find_min_idx_2(dp_grid[i-1])\n",
    "            print(min_val, min_idx, min2_val)\n",
    "            for j in range(n):\n",
    "                if j == min_idx:\n",
    "                    dp_grid[i][j] = grid[i][j] + min2_val\n",
    "                else:\n",
    "                    dp_grid[i][j] = grid[i][j] + min_val\n",
    "\n",
    "        ans = min(dp_grid[n-1])\n",
    "        return ans\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)  # 得到长度3 \n",
    "        print(n)\n",
    "        print('---')\n",
    "        f =[[0] * n for _ in range(n+1)]                 #在这个代码里,for _ in range(n + 1)中的_代表一个循环变量,但是在循环体中这个变量没有被用到。 #n=3 n+1=4了\n",
    "                                         # Python允许使用_来作为一个变量名,当你需要一个循环变量但是在循环体中不需要用到它时,就可以使用_来表示。 #3 *4就变成这样了\n",
    "        print(f)\n",
    "        print('f如上：')\n",
    "\n",
    "        for i, row in enumerate(grid,1):                #获取数组次序吧，以及对应行的数组\n",
    "            print(i,row)\n",
    "            print('---'*10)\n",
    "            for j,v in enumerate(row):              #获取什么我也不知道，不应该是2 个吗 #如果没有这个for的话 那上一个循环的结果，就是所有行的次序让后右边数组\n",
    "                print(j,v)                          #前面 i 不是次序第几行吗，后面row 就是数组\n",
    "                print('---'*15)                     #row 代表的不是数组吗，j就是列，v对应的是j相对应的数组中的数。\n",
    "                # x = min((f[i - 1][k] for k in range(n) if k != j), default=0)        #不是这什么意思啊，这是省略步骤吗，我不理解\n",
    "                min_f = float('inf')\n",
    "                for k in range(n):                   #n就是3,range 从0 开始,取出来的是0  1 2相当于列\n",
    "                    # print('这是k:',k,'这是j:',j)      #从上面来看j 就是列\n",
    "                    if k != j:                       # 最近的取的是相邻的这个列左右都可以，但是不能是同一列\n",
    "                        temp = f[i-1][k]\n",
    "                        # print('这是temp',temp)\n",
    "                        if temp < min_f:\n",
    "                            min_f = temp\n",
    "\n",
    "                x = min_f if min_f < float('inf') else 0\n",
    "                f[i][j] =v+x  \n",
    "        return min(f[n])                              \n",
    "# 这一行代码主要是求取上一行除当前列外的最小f值,用于更新当前f[i][j]。让我来详细解释一下:\n",
    "\n",
    "# 1. f[i-1] 取的是上一行的f数组\n",
    "\n",
    "# 2. [k for k in range(n) if k != j] 生成一个列表,包含了除当前列j之外的所有列的索引\n",
    "\n",
    "# 3. 所以 f[i-1][k] 取出的是上一行除当前列外的所有f值\n",
    "\n",
    "# 4. 对这个列表使用min()函数可以得到最小值\n",
    "\n",
    "# 5. default=0 表示如果这个列表为空,即除当前列外不再有其他列了,默认返回0\n",
    "\n",
    "# 举个例子,如果当前是第2行第3列(i=2, j=3),上一行f[1]是:\n",
    "\n",
    "# [0, 5, 2, 3, 4]\n",
    "\n",
    "# 那么 k for k in range(5) if k != 3 生成列表 [0,1,2,4] \n",
    "\n",
    "# 对应的值就是 [0, 5, 2, 4]\n",
    "\n",
    "# 取最小值 min() 得到 0\n",
    "\n",
    "# 所以这一行代码的作用就是从上一行中找出除当前列外最小的f值,赋值给x,用于更新当前f[i][j]。\n",
    "# min_f = float('inf')      #inf  正无穷\n",
    "# for k in range(n):\n",
    "#   if k != j:\n",
    "#     temp = f[i-1][k]\n",
    "#     if temp < min_f:\n",
    "#       min_f = temp\n",
    "\n",
    "# x = min_f if min_f < float('inf') else 0\n",
    "# 这是哪一行代码的普通人版本\n",
    "\n",
    "# f[i][j] 表示动态规划中的状态,即到达第i行第j列的当前最小路径和\n",
    "# v 是当前位置的数值,即 grid[i][j]\n",
    "# x 是上一行除当前列j外的最小f值\n",
    "# 根据动态规划的思想,要计算某个状态f[i][j],需要知道:\n",
    "\n",
    "# 当前位置的数值v\n",
    "# 已算出的上一个状态中的最优值x\n",
    "# 然后根据状态转移方程可以得到:\n",
    "\n",
    "# f[i][j] = v + x\n",
    "\n",
    "\n",
    "#all\n",
    "# 这段代码是实现 \"最小坠落路径和 II\" 这个题目的解法。\n",
    "\n",
    "# 题目的意思是:给你一个 n x n 的整数矩阵,从每一行中选一个数,要求从上到下选出一个路径,使路径上数字的和最小。每行只能选一个数,且不能重复选取同一列。\n",
    "\n",
    "# 这个解法的思路是:\n",
    "\n",
    "# 1. 使用动态规划。建立一个二维数组 f 来存储最小路径和。其中 f[i][j] 表示从第1行到第i行,在第i行选择第j列的最小路径和。\n",
    "\n",
    "# 2. 对于第 i 行的第 j 列,它的最小路径和 f[i][j] 就是:当前值 grid[i][j] 加上它上一行除了第j列以外最小的 f 值。\n",
    "\n",
    "# 3. 所以遍历每一行,使用 min() 来找到上一行除当前列以外的最小 f 值,加上当前值,就是该位置的最小路径和。\n",
    "\n",
    "# 4. 最后返回 f 数组最后一行的最小值,就是整个矩阵最小路径和。\n",
    "\n",
    "# 具体代码解析:\n",
    "\n",
    "# 1. 初始化 f 数组为全 0。\n",
    "\n",
    "# 2. 遍历每一行 grid,并列出该行的每个元素。\n",
    "\n",
    "# 3. 使用 min() 函数找到上一行除当前列外最小的 f 值,存为 x。\n",
    "\n",
    "# 4. 当前 f[i][j] 就是 x 加上当前值 grid[i][j]。\n",
    "\n",
    "# 5. 遍历完成后,f 数组最后一行就是每个列的最小路径和,返回最小值即可。\n",
    "\n",
    "# 这是一个典型的二维 DP 的解法,希望这个详细解析可以帮你理解这段代码的逻辑和算法思想。如果你有任何其他问题,欢迎再回复我。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        #动态规划\n",
    "        print(grid[0])\n",
    "        for i in range(1,row):\n",
    "            print(grid[i])\n",
    "            for j in range(col):\n",
    "                if j == 0:\n",
    "                    grid[i][j] = grid[i][j] + min(grid[i-1][1:])\n",
    "                elif j == col-1:\n",
    "                    grid[i][j] = grid[i][j] + min(grid[i-1][:col-1])\n",
    "                else:\n",
    "                    grid[i][j] = min(min(grid[i-1][0:j]),min(grid[i-1][j+1:])) + grid[i][j]\n",
    "        return min(grid[-1])\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if n ==1 :\n",
    "            return grid[0][0]\n",
    "        min1, min2 = 0, 0  \n",
    "        for i in range(n):\n",
    "            l= grid[i]\n",
    "            if i != 0:\n",
    "                for j in range(n):\n",
    "                    l[j] += min2 if grid[i-1][j] == min1 else min1\n",
    "            r = l.copy()\n",
    "            r.sort()\n",
    "            min1, min2 = r[0], r[1]\n",
    "            print(min1, min2, l)\n",
    "        return min1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "\n",
    "        @cache\n",
    "        def dp(i: int) -> List:\n",
    "            if i == n:\n",
    "                return [(0, -1), (0, n)]\n",
    "            (r1, i1), (r2, i2) = dp(i + 1)\n",
    "            re = []\n",
    "            for j in range(n):\n",
    "                if j == i1:\n",
    "                    re.append((r2 + grid[i][j], j))\n",
    "                else:\n",
    "                    re.append((r1 + grid[i][j], j))\n",
    "            return sorted(re)[:2]\n",
    "\n",
    "        return dp(0)[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "       \n",
    "        n = len(grid)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        dp[0] = [num for num in grid[0]]\n",
    "        print(dp)\n",
    "        for i in range(1,n) :\n",
    "            for j in range(n) :\n",
    "                tmp = copy.copy(dp[i-1])\n",
    "                del tmp[j]\n",
    "                dp[i][j] = min(tmp) + grid[i][j]\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        dp = [[inf]*n for i in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[0][i] = grid[0][i]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    if j == k:continue\n",
    "                    dp[i][j] = min(dp[i][j], dp[i-1][k] + grid[i][j])\n",
    "        print(dp)\n",
    "        return min(dp[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if n == 1:\n",
    "            return grid[0][0]\n",
    "        if n == 2:\n",
    "            return min(grid[0][1] + grid[1][0], grid[0][0] + grid[1][1])\n",
    "        # 每一行要么选最小，要么选倒数第二小\n",
    "        c = []\n",
    "        for i in grid:\n",
    "            tmp = list(sorted(range(n), key = lambda x:i[x]))\n",
    "            c.append((tmp[0], tmp[1], tmp[2]))\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            if i == 0: return grid[0][j]\n",
    "            # 第i行选j的最小和\n",
    "            res = inf\n",
    "            for k in c[i - 1]:\n",
    "                if k != j:\n",
    "                    res = min(res, f(i - 1, k) + grid[i][j])\n",
    "            return res\n",
    "        return min(f(n - 1, k) for k in c[-1])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        lenth = len(grid)\n",
    "        for i in range(1,lenth):\n",
    "            for j in range(lenth):\n",
    "                if j == 0:\n",
    "                    grid[i][j] += min(grid[i-1][1:])\n",
    "                elif j == lenth-1:\n",
    "                    grid[i][j] += min(grid[i-1][:lenth-1])\n",
    "                else:\n",
    "                    grid[i][j] += min(grid[i-1][:j]+grid[i-1][j+1:])\n",
    "        print(grid)\n",
    "        return min(grid[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        n = len(grid)\n",
    "        dp = [[0] * n for _ in range(n+1)]\n",
    "        for i, row in enumerate(grid, 1):\n",
    "            for j, v in enumerate(row):\n",
    "                x = float('inf')\n",
    "                for k in range(n):\n",
    "                    if k != j:\n",
    "                        x = min(dp[i-1][k], x)\n",
    "                if x == float('inf'):\n",
    "                    x = 0\n",
    "                dp[i][j] = x + v\n",
    "        print(dp)\n",
    "        return min(dp[n])\n",
    "                        \n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        dp = [[0]*n for i in range(n)]\n",
    "        dp[0] = grid[0]\n",
    "        for i in range(1,n):\n",
    "            for j in range(n):\n",
    "                temp = dp[i-1][j]\n",
    "                dp[i-1][j] = 1000000\n",
    "                dp[i][j] = grid[i][j] + min(dp[i-1])\n",
    "                dp[i-1][j] = temp\n",
    "        print(dp)\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "\n",
    "        dp = [[10**9 for _ in range(n)] for i in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[0][i] = grid[0][i]\n",
    "\n",
    "        for i in range(n):\n",
    "\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    if k != j:\n",
    "                        dp[i][j] = min(dp[i][j],dp[i-1][k]+grid[i][j])\n",
    "\n",
    "        print(dp)\n",
    "        return  min(dp[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        d = [[inf for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            d[0][i] = grid[0][i]\n",
    "        for i in range(1,n):\n",
    "            for j in range(n):\n",
    "                li=d[i-1]\n",
    "                if li[:j]:\n",
    "                    value1=min(d[i-1][:j])\n",
    "                else:\n",
    "                    value1=inf \n",
    "                if li[j+1:]:\n",
    "                    value2=min(d[i-1][j+1:])\n",
    "                else:\n",
    "                    value2=inf\n",
    "                d[i][j] = min(d[i][j], min(value1,value2) + grid[i][j])\n",
    "        print(d)\n",
    "        return min(d[n - 1])\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        # path = []\n",
    "        # self.res = 20000\n",
    "        # n = len(grid)\n",
    "        # # visited = [[0] * n] * n\n",
    "        # def dfs(node):\n",
    "        #     if node[0] == n-1:\n",
    "        #         self.res = min(self.res, sum(path))\n",
    "        #         return\n",
    "\n",
    "        #     # visited[node[0]][node[1]] == 1\n",
    "        #     for j in range(n):\n",
    "        #         if j != node[1]:\n",
    "        #             path.append(grid[node[0]+1][j])\n",
    "        #             dfs([node[0]+1, j])\n",
    "        #             path.pop()\n",
    "        \n",
    "        # for i in range(n):\n",
    "        #     path.append(grid[0][i])\n",
    "        #     dfs([0,i])\n",
    "        #     path.pop()\n",
    "        # return self.res\n",
    "\n",
    "        n = len(grid)\n",
    "        dp = [[10**9 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[0][i] = grid[0][i]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    if j==k:\n",
    "                        continue\n",
    "                    dp[i][j] = min(dp[i][j], dp[i-1][k] + grid[i][j])\n",
    "        print(dp)\n",
    "        return min(dp[-1])\n",
    "\n",
    "        # n = len(grid)\n",
    "        # d = [[10**9 for _ in range(n)] for _ in range(n)]\n",
    "        # for i in range(n):\n",
    "        #     d[0][i] = grid[0][i]\n",
    "        # for i in range(1, n):\n",
    "        #     for j in range(n):\n",
    "        #         for k in range(n):\n",
    "        #             if j == k:\n",
    "        #                 continue\n",
    "        #             d[i][j] = min(d[i][j], d[i - 1][k] + grid[i][j])\n",
    "        # print(d)\n",
    "        # return min(d[n - 1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        dp = [[0]*n for _ in range(n-1)]\n",
    "        dp.append(grid[n-1][:])\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(n):\n",
    "                t = 20000\n",
    "                for k in range(n):\n",
    "                    if k==j:\n",
    "                        continue\n",
    "                    t = min(t,dp[i+1][k])\n",
    "                dp[i][j]=grid[i][j]+t\n",
    "        print(dp)\n",
    "        return min(dp[0])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        d = [[10 ** 9 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            d[0][i] = grid[0][i]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    if j == k:\n",
    "                        continue\n",
    "                    d[i][j] = min(d[i][j], d[i - 1][k] + grid[i][j])\n",
    "        print(d)\n",
    "        return min(d[n - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, nums: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [[inf] * n for _ in range(n)]\n",
    "        for j in range(n):\n",
    "            f[0][j] = nums[0][j]\n",
    "        for i in range(1, n):\n",
    "            d1, d2 = inf, inf\n",
    "            for j in range(n):\n",
    "                x = f[i - 1][j]\n",
    "                if x <= d1:\n",
    "                    d2 = d1\n",
    "                    d1 = x\n",
    "                elif x < d2:\n",
    "                    d2 = x\n",
    "            for j in range(n):\n",
    "                if f[i - 1][j] == d1:\n",
    "                    f[i][j] = d2 + nums[i][j]\n",
    "                else:\n",
    "                    f[i][j] = d1 + nums[i][j]\n",
    "        print(f)\n",
    "        return min(f[n - 1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n=len(matrix)\n",
    "        dp=[[0]*n for i in range(2)]\n",
    "        dp[0]=matrix[0]\n",
    "        for i in range(1,n):\n",
    "            for j in range(n):\n",
    "                if j==0:\n",
    "                    dp[1][j]=min(dp[0][j],dp[0][j+1])+matrix[i][j]\n",
    "                elif j<n-1:\n",
    "                    dp[1][j]=min(dp[0][j-1],dp[0][j],dp[0][j+1])+matrix[i][j]\n",
    "                else:\n",
    "                    dp[1][j]=min(dp[0][j-1],dp[0][j])+matrix[i][j]\n",
    "            dp[0]=dp[1][:]\n",
    "        return min(dp[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        prev = [0]*n\n",
    "        for i in range (0,n):\n",
    "            cur = []\n",
    "            for j in range (0,n):\n",
    "                if j ==0:\n",
    "                    if n  == 1:\n",
    "                        cur.append(matrix[0][0])\n",
    "                        continue\n",
    "                    cur.append(matrix[i][0]+min([prev[0],prev[1]]))\n",
    "                    continue\n",
    "                if j== n-1:\n",
    "                    cur.append(matrix[i][j]+min([prev[j],prev[j-1]]))\n",
    "                    continue\n",
    "                \n",
    "                cur.append(matrix[i][j]+min([prev[j],prev[j-1],prev[j+1]]))\n",
    "            prev = cur\n",
    "        return min(prev)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n=len(matrix)\n",
    "        a=[0]*n\n",
    "        for row in matrix:\n",
    "            b=[0]*n\n",
    "            for j,x in enumerate(row):\n",
    "                l,r=max(0,j-1),min(n,j+2)\n",
    "                b[j]=min(a[l:r])+x\n",
    "            a=b\n",
    "        return min(a)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        dp = [[0] * n for _ in range(2)]\n",
    "        dp[0] = matrix[0]\n",
    "        for i in range(1, n):\n",
    "            cur, prev = i % 2, 1 - i % 2\n",
    "            dp[cur][0] = min(dp[prev][0], dp[prev][1]) + matrix[i][0]\n",
    "            for j in range(1, n - 1):\n",
    "                dp[cur][j] = min(dp[prev][j-1], dp[prev][j], dp[prev][j+1]) + matrix[i][j]\n",
    "            dp[cur][n-1] = min(dp[prev][n-2], dp[prev][n-1]) + matrix[i][-1]\n",
    "\n",
    "        return min(dp[(n-1)%2])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        if n == 1:\n",
    "            return matrix[0][0]\n",
    "\n",
    "        matrix_sum = []\n",
    "        matrix_sum.append(matrix[0])\n",
    "\n",
    "        for i in range(1, n):\n",
    "            current_row = [0] * n\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    current_row[j] = matrix[i][j] + min(matrix_sum[i-1][j], matrix_sum[i-1][j+1])\n",
    "                elif j == n-1:\n",
    "                    current_row[j] = matrix[i][j] + min(matrix_sum[i-1][j], matrix_sum[i-1][j-1])\n",
    "                else:\n",
    "                    current_row[j] = matrix[i][j] + min(matrix_sum[i-1][j+1], matrix_sum[i-1][j-1], matrix_sum[i-1][j])\n",
    "\n",
    "            matrix_sum.append(current_row)\n",
    "\n",
    "        final_result = matrix_sum[n-1][0]\n",
    "        for value in matrix_sum[n-1]:\n",
    "            final_result = value if value < final_result else final_result\n",
    "\n",
    "        return final_result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        if n == 1:\n",
    "            return matrix[0][0]\n",
    "        for i in range(1, n):\n",
    "            matrix[i][0] += min(matrix[i-1][0], matrix[i-1][1])\n",
    "            matrix[i][n-1] += min(matrix[i-1][n-1], matrix[i-1][n-2])\n",
    "            for j in range(1, n-1):\n",
    "                matrix[i][j] += min(matrix[i-1][j-1], matrix[i-1][j], matrix[i-1][j+1])\n",
    "        print(matrix)\n",
    "        return min(matrix[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        for i in range(1,m):\n",
    "            for j in range(n):\n",
    "                tmp=inf\n",
    "                for fi,fj in [(i-1,j-1),(i-1,j),(i-1,j+1)]:\n",
    "                    if 0<=fi<m and 0<=fj<n:\n",
    "                        tmp=min(tmp,matrix[i][j]+matrix[fi][fj])\n",
    "                matrix[i][j]=tmp\n",
    "        print(matrix)\n",
    "        return min(matrix[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "\n",
    "        if len(matrix) == 1:\n",
    "            return matrix[0][0]\n",
    "\n",
    "        # [100,-42,-46, -41]\n",
    "        # [31,  97, 10, -10]\n",
    "        # [-58,-51, 82,  89]\n",
    "        # [51,  81, 69, -51]\n",
    "        #\n",
    "\n",
    "        dp = [[0] * len(matrix) for _ in matrix]\n",
    "        for index_i, line in enumerate(matrix):\n",
    "            if index_i == 0:\n",
    "                dp[0] = line\n",
    "                continue\n",
    "\n",
    "            for index_j, item in enumerate(line):\n",
    "                if index_j == 0:\n",
    "                    dp[index_i][index_j] = item + min(\n",
    "                        dp[index_i - 1][index_j],\n",
    "                        dp[index_i - 1][index_j + 1]\n",
    "                    )\n",
    "                elif index_j == len(line) - 1:\n",
    "                    dp[index_i][index_j] = item + min(\n",
    "                        dp[index_i - 1][index_j],\n",
    "                        dp[index_i - 1][index_j - 1]\n",
    "                    )\n",
    "                else:\n",
    "                    dp[index_i][index_j] = item + min(\n",
    "                        dp[index_i - 1][index_j],\n",
    "                        dp[index_i - 1][index_j - 1],\n",
    "                        dp[index_i - 1][index_j + 1]\n",
    "                    )\n",
    "\n",
    "        print(dp)\n",
    "        return min(dp[-1])\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        result = [[101]+matrix[0]+[101]]\n",
    "        for i in range(1,n):\n",
    "            result.append([101*(i+1)]+[0]*n+[101*(i+1)])\n",
    "        print(result)\n",
    "        for i in range(1,n):\n",
    "            for j in range(1,n+1):\n",
    "                print(i,j)\n",
    "                num1 = matrix[i][j-1]+result[i-1][j] \n",
    "                num2 = matrix[i][j-1]+result[i-1][j-1] \n",
    "                num3 = matrix[i][j-1]+result[i-1][j+1] \n",
    "                result[i][j] = min(num1,num2,num3)\n",
    "        print(result)\n",
    "        print(result[n-1][1:-1])\n",
    "        return min(result[n-1][1:-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        l = len(matrix)\n",
    "        if l ==1:\n",
    "            return matrix[0][0]\n",
    "\n",
    "        def getmin(i):\n",
    "            cur = [0]*l\n",
    "            if i == l:\n",
    "                return cur\n",
    "            pre = getmin(i+1)\n",
    "            cur[0] = matrix[i][0]+min([pre[0],pre[1]])\n",
    "            cur[-1] = matrix[i][-1]+min([pre[-1],pre[-2]])\n",
    "            for j in range(1,l-1):\n",
    "                cur[j] = matrix[i][j]+min([pre[j-1],pre[j],pre[j+1]])\n",
    "            return cur\n",
    "\n",
    "        res = min(getmin(0))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "            # 计算长度\n",
    "            n = len(matrix)\n",
    "                # 数据校验\n",
    "            if n == 1:\n",
    "                return matrix[0][0]\n",
    "            dp = [[0 for y in range(0, n)] for x in range(0, n +1)]\n",
    "            for x in range(1, n + 1):\n",
    "                print(\"================\")\n",
    "                print(x)\n",
    "                for y in range(0, n):\n",
    "                    print(\"y:{}\".format(y))\n",
    "                    if y == 0:\n",
    "                        dp[x][y] = min(dp[x - 1][y] + matrix[x - 1][y],\n",
    "                                    dp[x - 1][y + 1] + matrix[x - 1][y + 1])\n",
    "                    elif y == n-1:\n",
    "                        dp[x][y] = min(dp[x - 1][y - 1] + matrix[x - 1][y - 1], dp[x - 1][y] + matrix[x - 1][y])\n",
    "                    else:\n",
    "                        dp[x][y] = min(dp[x - 1][y - 1] + matrix[x - 1][y - 1], dp[x - 1][y] + matrix[x - 1][y],\n",
    "                                    dp[x - 1][y + 1] + matrix[x - 1][y + 1])\n",
    "            print(dp)\n",
    "            for y in range(0, n):\n",
    "                dp[n-1][y] = dp[n-1][y] + matrix[n-1][y]\n",
    "\n",
    "            print(dp)\n",
    "            return min(dp[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        row = column = len(matrix)\n",
    "        dp = {(0,c):matrix[0][c] for c in range(column)}\n",
    "        for r in range(1, row):\n",
    "            for c in range(column):\n",
    "                if c == 0:\n",
    "                    dp[(r,c)] = min(dp[(r-1,c)],dp[(r-1,c+1)]) + matrix[r][c]\n",
    "                elif c == column - 1:\n",
    "                    dp[(r,c)] = min(dp[(r-1,c-1)],dp[(r-1,c)]) + matrix[r][c]\n",
    "                else:\n",
    "                    dp[(r,c)] = min(dp[(r-1,c-1)],dp[(r-1,c)],dp[(r-1,c+1)]) + matrix[r][c]\n",
    "        res = list()\n",
    "        for key,value in dp.items():\n",
    "            if key[0] == row - 1:\n",
    "                res.append(value)\n",
    "        return min(res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        mem_dic = {}\n",
    "        for i in range(len(matrix[0])):\n",
    "            mem_dic[(0,i)] = matrix[0][i]\n",
    "        for i in range(1, len(matrix)):\n",
    "            for j in range(len(matrix[i])):\n",
    "                cand1 = mem_dic.get((i-1,j-1), float('inf'))\n",
    "                cand2 = mem_dic.get((i-1,j))\n",
    "                cand3 = mem_dic.get((i-1,j+1), float('inf'))\n",
    "                mem_dic[(i,j)] = min(cand1,cand2,cand3)+matrix[i][j]\n",
    "        \n",
    "        mini_val = float('inf')\n",
    "        for j in range(len(matrix[0])):\n",
    "            mini_val = min(mini_val, mem_dic[(len(matrix)-1, j)])\n",
    "        return mini_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        self.d = {}\n",
    "        if matrix ==None or len(matrix) == 0:\n",
    "            return 0\n",
    "        for col in range(len(matrix[0])):\n",
    "            self.d[str(len(matrix)-1) + \"_\" +str(col)] = matrix[len(matrix)-1][col]\n",
    "        \n",
    "        res = 9999999\n",
    "        for i in range(len(matrix[0])):\n",
    "            res = min(res, self.dp(matrix, 0, i))\n",
    "        return res\n",
    "    \n",
    "    \n",
    "    def dp(self, matrix, row, col):\n",
    "        if row == len(matrix)-1:\n",
    "            return self.d[str(row) + \"_\" +str(col)]\n",
    "        if str(row) + \"_\" +str(col) in self.d:\n",
    "            return self.d[str(row) + \"_\" +str(col)]\n",
    "        \n",
    "        if col-1 >= 0:\n",
    "            tmp1 = self.dp(matrix, row+1, col-1)\n",
    "        else:\n",
    "            tmp1 = 9999999\n",
    "        \n",
    "        tmp2 = self.dp(matrix, row+1, col)\n",
    "        if col+1 <= len(matrix[0])-1:\n",
    "            tmp3 = self.dp(matrix, row+1, col+1)\n",
    "        else:\n",
    "            tmp3 = 9999999\n",
    "        tmp = min(min(tmp1, tmp2),tmp3)\n",
    "        self.d[str(row) + \"_\" +str(col)] = tmp + matrix[row][col]\n",
    "        return self.d[str(row) + \"_\" +str(col)]\n",
    "        \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        self.d = {}\n",
    "        if matrix ==None or len(matrix) == 0:\n",
    "            return 0\n",
    "        for col in range(len(matrix[0])):\n",
    "            self.d[str(len(matrix)-1) + \"_\" +str(col)] = matrix[len(matrix)-1][col]\n",
    "        \n",
    "        res = 9999999\n",
    "        for i in range(len(matrix[0])):\n",
    "            res = min(res, self.dp(matrix, 0, i))\n",
    "        return res\n",
    "    \n",
    "    \n",
    "    def dp(self, matrix, row, col):\n",
    "        if row == len(matrix)-1:\n",
    "            return self.d[str(row) + \"_\" +str(col)]\n",
    "        if str(row) + \"_\" +str(col) in self.d:\n",
    "            return self.d[str(row) + \"_\" +str(col)]\n",
    "        \n",
    "        if col-1 >= 0:\n",
    "            tmp1 = self.dp(matrix, row+1, col-1)\n",
    "        else:\n",
    "            tmp1 = 9999999\n",
    "        \n",
    "        tmp2 = self.dp(matrix, row+1, col)\n",
    "        if col+1 <= len(matrix[0])-1:\n",
    "            tmp3 = self.dp(matrix, row+1, col+1)\n",
    "        else:\n",
    "            tmp3 = 9999999\n",
    "        tmp = min(min(tmp1, tmp2),tmp3)\n",
    "        self.d[str(row) + \"_\" +str(col)] = tmp + matrix[row][col]\n",
    "        return self.d[str(row) + \"_\" +str(col)]\n",
    "        \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        df = {}\n",
    "        res = []\n",
    "\n",
    "        for i in range(0, n):\n",
    "            for j in range(0, n):\n",
    "                if i == 0:\n",
    "                   df[(i, j)] = matrix[i][j]\n",
    "                elif j == 0:\n",
    "                    df[(i, j)] = min(df[(i - 1, j)], df[(i - 1, j + 1)]) + matrix[i][j]\n",
    "                elif j == n - 1:\n",
    "                    df[(i, j)] = min(df[(i - 1, j)], df[(i - 1, j - 1)]) + matrix[i][j] \n",
    "                else:\n",
    "                    df[(i, j)] = min(df[(i - 1, j)], df[(i - 1, j - 1)], df[(i - 1, j + 1)]) + matrix[i][j]\n",
    "                print(df[(i, j)], end = ' ')\n",
    "        \n",
    "        for i in range(0, n):\n",
    "            res.append(df[(n - 1, i)])\n",
    "\n",
    "        return min(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        def dp(matrix, i, j):\n",
    "            if i < 0 or j < 0 or i >= len(matrix) or j >= len(matrix):\n",
    "                return float('inf')\n",
    "            \n",
    "            if i == 0:\n",
    "                return matrix[i][j]\n",
    "\n",
    "            if memo[i][j] != 9999:\n",
    "                return memo[i][j]\n",
    "            \n",
    "            memo[i][j] = matrix[i][j] + min(min(dp(matrix, i - 1, j - 1), \n",
    "                    dp(matrix, i - 1, j)), dp(matrix, i - 1, j + 1))\n",
    "            return memo[i][j]\n",
    "\n",
    "            \n",
    "\n",
    "        n = len(matrix)\n",
    "        res = float('inf')\n",
    "        memo = [[9999] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            res = min(res, dp(matrix, n - 1, i))\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        lent = len(matrix)\n",
    "        if lent<2:\n",
    "            return min(matrix[0])\n",
    "        self.res = [[100*101]*lent for _ in range(lent)]\n",
    "        self.count = 100*101\n",
    "        def dp(indx,indy):\n",
    "            if indx<0 or indy<0 or indy>=len(matrix):\n",
    "                return 100*100\n",
    "            if indx ==0:\n",
    "                return matrix[0][indy]\n",
    "            if self.res[indx][indy]!=100*101:\n",
    "                return self.res[indx][indy]\n",
    "            self.res[indx][indy] = matrix[indx][indy] +min([dp(indx-1,indy),dp(indx-1,indy-1),dp(indx-1,indy+1)])\n",
    "            return self.res[indx][indy]\n",
    "        \n",
    "        for i in range(lent):\n",
    "            # if \n",
    "            self.res[lent-1][i] =matrix[lent-1][i] +min([dp(lent-2,i),dp(lent-2,i-1),dp(lent-2,i+1)])\n",
    "            # self.count =min(self.count,matrix[lent-1][i] +min([dp(lent-2,i),dp(lent-2,i-1),dp(lent-2,i+1)]))\n",
    "        return min(self.res[lent-1]) #self.count\n",
    "        # 接近暴力\n",
    "        # lent = len(matrix)\n",
    "        # if lent<2:\n",
    "        #     return min(matrix[0])\n",
    "        # self.res = 100*100#[100*100]*lent\n",
    "        # def dp(indx,indy):\n",
    "        #     if indx<0 or indy<0 or indy>=len(matrix):\n",
    "        #         return 100*100\n",
    "        #     if indx ==0:\n",
    "        #         return matrix[0][indy]\n",
    "        #     return matrix[indx][indy] +min([dp(indx-1,indy),dp(indx-1,indy-1),dp(indx-1,indy+1)])\n",
    "        \n",
    "        # for i in range(lent):\n",
    "        #     # if \n",
    "        #     # self.res[i] =matrix[lent-1][i] +min([dp(lent-2,i),dp(lent-2,i-1),dp(lent-2,i+1)])\n",
    "        #     self.res =min(self.res,matrix[lent-1][i] +min([dp(lent-2,i),dp(lent-2,i-1),dp(lent-2,i+1)]))\n",
    "        # return self.res\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        memo = [[99999] * n for _ in range(n)]\n",
    "\n",
    "        def dp(matrix, i, j):\n",
    "            if i < 0 or i >= n or j < 0 or j >= n:\n",
    "                return 99999\n",
    "            \n",
    "            if i == 0:\n",
    "                return matrix[i][j]\n",
    "            \n",
    "            if memo[i][j] != 99999:\n",
    "                return memo[i][j]\n",
    "\n",
    "            memo[i][j] = matrix[i][j] + min(\n",
    "                        dp(matrix, i - 1, j - 1),\n",
    "                        dp(matrix, i - 1, j),\n",
    "                        dp(matrix, i - 1, j + 1)\n",
    "                    )\n",
    "\n",
    "            return memo[i][j]\n",
    "        \n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            res = min(res, dp(matrix, n - 1, i))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        ans, n = inf, len(matrix)\n",
    "        dp = [[inf] * n for _ in range(n)]\n",
    "        def dfs(i, j):\n",
    "            if j < 0 or j >= n:\n",
    "                return inf\n",
    "            if i == 0:\n",
    "                return matrix[i][j]\n",
    "            if dp[i][j] != inf:\n",
    "                return dp[i][j]\n",
    "            res = min(dfs(i-1, j), dfs(i-1, j-1), dfs(i-1, j+1)) + matrix[i][j]\n",
    "            dp[i][j] = res\n",
    "            return res\n",
    "        for i in range(n):\n",
    "            ans = min(dfs(n-1, i), ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        def dp(i, j):\n",
    "            if i<0 or j<0 or i>n-1 or j>n-1:\n",
    "                return 10001\n",
    "            if i == n-1:\n",
    "                return matrix[i][j]\n",
    "            if memo[i][j] != 10002:\n",
    "                return memo[i][j]\n",
    "            memo[i][j] = matrix[i][j] + min(dp(i+1, j-1), min(dp(i+1, j), dp(i+1, j+1)))\n",
    "            return memo[i][j]\n",
    "        \n",
    "        n = len(matrix)\n",
    "        res = float('inf')\n",
    "        memo = [[10002 for _ in range(n)] for _ in range(n)]\n",
    "        for j in range(n):\n",
    "            res = min(res, dp(0, j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        memo = [[-111 for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        def dp(i, j):\n",
    "            if i < 0 or j < 0 or i >= n or j >= n:\n",
    "                return float('INF')\n",
    "            if i == 0:\n",
    "                return matrix[0][j]\n",
    "\n",
    "            if memo[i][j] != -111:\n",
    "                return memo[i][j]\n",
    "\n",
    "            # i,j 的正上，坐上，右上位置\n",
    "            a = dp(i-1, j-1)\n",
    "            b = dp(i-1, j)\n",
    "            c = dp(i-1, j+1)\n",
    "\n",
    "            # 上面边界判断，非法就设置最大值\n",
    "            if i - 1 < 0 or j - 1 < 0:\n",
    "                a = float('INF')\n",
    "            if i - 1 < 0:\n",
    "                b = float('INF')\n",
    "            if i - 1 < 0 or j + 1 >= n:\n",
    "                c = float('INF')\n",
    "\n",
    "            memo[i][j] = min(a, b, c) + matrix[i][j]\n",
    "\n",
    "            return memo[i][j]\n",
    "\n",
    "        res = float('INF')\n",
    "        for ii in range(n):\n",
    "            # 写死最后一行n-1，遍历不同列\n",
    "            res = min(res, dp(n-1, ii))\n",
    "\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        dp={}\n",
    "        ku={}\n",
    "        n=len(matrix)\n",
    "        m=len(matrix[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ku[(i,j)]=matrix[i][j]\n",
    "        def f(i,j):\n",
    "            if i==0:\n",
    "                return matrix[i][j]\n",
    "            else:\n",
    "                single=[]\n",
    "                if dp.get((i-1,j))!=None:\n",
    "                    single+=[dp.get((i-1,j))]\n",
    "                if dp.get((i-1,j-1))!=None:\n",
    "                    single+=[dp.get((i-1,j-1))]\n",
    "                if dp.get((i-1,j+1))!=None:\n",
    "                    single+=[dp.get((i-1,j+1))]\n",
    "            return min(single)+matrix[i][j]\n",
    "        result=[]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                dp[(i,j)]=f(i,j)\n",
    "                if i==n-1:\n",
    "                    result+=[dp[(i,j)]]\n",
    "        print(dp)\n",
    "        return min(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from xmlrpc.client import MAXINT\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: [[int]]) -> int:\n",
    "        if len(matrix) == 0: return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [[0] * (n+2) for _ in range(m+1)]\n",
    "        ans = MAXINT\n",
    "        for i in range(m+1):\n",
    "            dp[i][0] = MAXINT\n",
    "            dp[i][-1] = MAXINT\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]) + matrix[i-1][j-1]\n",
    "                if i == m:\n",
    "                    ans = min(ans, dp[i][j])\n",
    "        return ans\n",
    "\n",
    "print(Solution().minFallingPathSum([[2,1,3],[6,5,4],[7,8,9]]))                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: list[list[int]]) -> int:\n",
    "        \"\"\"\n",
    "        >>> a = Solution_recursion()\n",
    "        >>> a.minFallingPathSum([[2,1,3],[6,5,4],[7,8,9]])\n",
    "        13\n",
    "        \"\"\"\n",
    "        row, column = len(matrix), len(matrix[0])\n",
    "        map = [[None for i in range(column)] for j in range(row)]\n",
    "        def helper(x, y):\n",
    "            if y < 0 : return helper(x, y+1)\n",
    "            if y > column-1: return helper(x, y-1)\n",
    "            if x == row-1: return matrix[x][y]\n",
    "            if map[x][y] != None: return map[x][y]\n",
    "\n",
    "            minimal_for_helper = helper(x+1, y-1)\n",
    "            for i in [0, 1]:\n",
    "                minimal_for_helper = min(minimal_for_helper, helper(x+1, y+i))\n",
    "            map[x][y] = matrix[x][y] + minimal_for_helper\n",
    "            return map[x][y]\n",
    "        minimal = helper(0, 0)\n",
    "        for i in range(1, column):\n",
    "            minimal = min(minimal, helper(0, i))\n",
    "        return minimal\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minFallingPathSum(self, A: List[List[int]]) -> int:\n",
    "        MAX_LONG_INT = 2147483647\n",
    "        row = len(A)\n",
    "        col = row\n",
    "        def right_point(row_i,col_j):\n",
    "            return 0<= row_i < row and 0<= col_j < row\n",
    "        res = []\n",
    "        reached_node_min_path_sum = {}\n",
    "        def dfs(i, j, *argc, **argv):\n",
    "\n",
    "            if not right_point(i,j):\n",
    "                if i==row:\n",
    "                    return 0 \n",
    "                else:\n",
    "                    return MAX_LONG_INT\n",
    "\n",
    "            if (i, j) in reached_node_min_path_sum:\n",
    "                return reached_node_min_path_sum[(i, j)]\n",
    "\n",
    "            min_path_sum = A[i][j]\n",
    "            min_path_sum += min(dfs(i+1,j),\n",
    "                               dfs(i+1,j-1),\n",
    "                               dfs(i+1,j+1))\n",
    "\n",
    "            reached_node_min_path_sum[(i, j)] = min_path_sum\n",
    "            return min_path_sum\n",
    "\n",
    "\n",
    "        res_li = []\n",
    "        result = MAX_LONG_INT\n",
    "        for j in range(col):\n",
    "            result = min(result, dfs(0,j,0,0))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.matrix = None\n",
    "        self.n = 0\n",
    "\n",
    "    @lru_cache(10000)\n",
    "    def route(self, row, col) -> int:\n",
    "        if row == self.n - 1:\n",
    "            return self.matrix[row][col]\n",
    "        a, b, c = inf, inf, inf\n",
    "        if not col - 1 < 0:\n",
    "            a = self.route(row + 1, col - 1)\n",
    "        b = self.route(row + 1, col)\n",
    "        if not col + 1 >= self.n:\n",
    "            c = self.route(row + 1, col + 1)\n",
    "        return self.matrix[row][col] + min([a, b, c])\n",
    "\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        self.matrix = matrix\n",
    "        self.n = len(matrix)\n",
    "        return min([self.route(0, i) for i in range(self.n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, A: List[List[int]]) -> int:\n",
    "        def cached(f):\n",
    "            cache = {}\n",
    "            def wrapper(*args):\n",
    "                if args not in cache:\n",
    "                    cache[args] = f(*args)\n",
    "                return cache[args]\n",
    "            return wrapper\n",
    "        \n",
    "        @cached\n",
    "        def f(x, y):\n",
    "            if x < 0:\n",
    "                return 0\n",
    "            if y < 0 or y >= len(A[0]):\n",
    "                return float('inf')\n",
    "            return A[x][y] + min(f(x-1, y-1), f(x-1, y), f(x-1, y+1))\n",
    "        \n",
    "        return min([f(len(A)-1, y) for y in range(len(A[0]))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, A: List[List[int]]) -> int:\n",
    "        n, m = len(A), len(A[0])\n",
    "        import functools\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            nonlocal n, m\n",
    "            # print(i, j)\n",
    "            ans = float('inf')\n",
    "            if i + 1 < n:\n",
    "                ans = min(ans, dfs(i + 1, j))\n",
    "                if j + 1 < m:\n",
    "                    ans = min(ans, dfs(i + 1, j + 1))\n",
    "                if j - 1 >= 0:\n",
    "                   ans = min(ans, dfs(i + 1, j - 1))\n",
    "\n",
    "            ans = 0 if ans == float('inf') else ans\n",
    "            return  ans + A[i][j]\n",
    "        \n",
    "        ans = float('inf')\n",
    "        for i in range(m):\n",
    "            # print(0, i)\n",
    "            ans = min(ans, dfs(0, i))\n",
    "        \n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, A: List[List[int]]) -> int:\n",
    "        rec = {}\n",
    "        def helper(index):\n",
    "            if index in rec:\n",
    "                return rec[index]\n",
    "            a,b = index\n",
    "            if a == len(A) - 1 and 0 <= b < len(A[0]):\n",
    "                return A[a][b]\n",
    "            if b < 0 or b >= len(A[0]):\n",
    "                return 101\n",
    "            l = A[a][b] + min(helper((a + 1, b)), helper((a + 1, b + 1)), helper((a + 1, b - 1)))\n",
    "            rec[index] = l\n",
    "            return l\n",
    "        res = 101\n",
    "        for i in range(len(A[0])):\n",
    "            res = min(res, helper((0, i)))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, A: List[List[int]]) -> int:\n",
    "        size = len(A)\n",
    "        \n",
    "        memo = dict()\n",
    "\n",
    "        def dfs(m, n):\n",
    "            if m < 0 or m >= size or n < 0 or n >= size:\n",
    "                return float('inf')\n",
    "\n",
    "            if m == 0:\n",
    "                return A[m][n]\n",
    "\n",
    "            if (m, n) in memo:\n",
    "                return memo[(m, n)]\n",
    "\n",
    "            minVal = min(dfs(m-1, n-1), dfs(m-1, n), dfs(m-1, n+1)) + A[m][n]\n",
    "\n",
    "            memo[(m ,n)] = minVal\n",
    "\n",
    "            return minVal\n",
    "\n",
    "        globalMin = float('inf')\n",
    "        for i in range(size):\n",
    "            globalMin = min(globalMin, dfs(size-1, i))\n",
    "\n",
    "        return globalMin\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        memo={}\n",
    "        n=len(matrix)\n",
    "        def minWay(lst,i,j):\n",
    "            if len(lst)==1:\n",
    "                return lst[0][0]\n",
    "            if i==0:\n",
    "                return lst[0][j]\n",
    "            if i*1000+j in memo:\n",
    "                return memo[i*1000+j]\n",
    "            if j==0:\n",
    "                memo[i*1000+j]=min(minWay(lst,i-1,0),minWay(lst,i-1,1))+lst[i][0]\n",
    "                return min(minWay(lst,i-1,0),minWay(lst,i-1,1))+lst[i][0]\n",
    "            if j==len(lst)-1:\n",
    "                memo[i*1000+j]=min(minWay(lst,i-1,j-1),minWay(lst,i-1,j))+lst[i][j]\n",
    "                return min(minWay(lst,i-1,j-1),minWay(lst,i-1,j))+lst[i][j]\n",
    "            memo[i*1000+j]=min(minWay(lst,i-1,j-1),minWay(lst,i-1,j),minWay(lst,i-1,j+1))+lst[i][j]\n",
    "            return min(minWay(lst,i-1,j-1),minWay(lst,i-1,j),minWay(lst,i-1,j+1))+lst[i][j]\n",
    "\n",
    "\n",
    "        minsum=minWay(matrix,n-1,0)\n",
    "        for i in range(n):\n",
    "            if minWay(matrix,n-1,i)<minsum:\n",
    "                minsum=minWay(matrix,n-1,i)\n",
    "        return minsum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, A: List[List[int]]) -> int:\n",
    "        if not A:\n",
    "            return 0\n",
    "        m, n = len(A), len(A[0])\n",
    "\n",
    "        from functools import lru_cache\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def recur(row, col):\n",
    "            if row == m:\n",
    "                return 0\n",
    "            return min(recur(row+1, i) for i in (col - 1, col, col + 1) if 0 <= i < n) + A[row][col]\n",
    "\n",
    "        return min(recur(0, i) for i in range(0, n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        mem = {}\n",
    "\n",
    "        def dp(i, j):\n",
    "            # if not 0<=i<n or not 0<=j<n:\n",
    "                # return float('inf')\n",
    "            if i == n-1:\n",
    "                return 0\n",
    "            \n",
    "            pos = str(i)+'-'+str(j)\n",
    "            if pos in mem: return mem[pos]\n",
    "\n",
    "            res = float('inf')\n",
    "            for r, c in [[1, -1], [1, 0], [1, 1]]:\n",
    "                if not 0<=i+r<n or not 0<=j+c<n:\n",
    "                    continue\n",
    "                res = min(res, dp(i+r, j+c)+matrix[i+r][j+c])\n",
    "            \n",
    "            mem[pos] = res\n",
    "            return mem[pos]\n",
    "        \n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            res = min(res, dp(0, i)+matrix[0][i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        # dp数组 定义dp为从matrix[0,..]往下落，落到matrix[i,j]的最小路径为 dp(matrix, i, j)\n",
    "        n = len(matrix)\n",
    "        m = len(matrix[0])\n",
    "        res = float(inf)\n",
    "        dict1 = dict()\n",
    "        # 建立dp 建立备忘录dict1 防止重复计算\n",
    "        def dp(matrix, i, j):\n",
    "            # 非法的索引的定位\n",
    "            if i < 0 or j < 0 or i >= n or j >= m:\n",
    "                return 99999\n",
    "            # base 从第0行下落 落到0, j的最小路径就是本身\n",
    "            if i == 0:\n",
    "                # print(j)\n",
    "                return matrix[i][j]\n",
    "            if (i, j) in dict1:\n",
    "                return dict1[(i, j)]\n",
    "            dict1[(i, j)] = matrix[i][j] + min(dp(matrix, i-1, j-1), \n",
    "                                                dp(matrix, i-1, j), dp(matrix, i-1, j+1))\n",
    "            return dict1[(i, j)]\n",
    "        # 终点可能在最后一行的任意列\n",
    "        for j in range(m):\n",
    "            res = min(res, dp(matrix, n-1, j))\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        def dp(matrix, i, j):\n",
    "            if i < 0 or j < 0 or i > len(matrix) - 1 or j > len(matrix) - 1:\n",
    "                return 10001\n",
    "            if i == 0:\n",
    "                return matrix[i][j]\n",
    "            name = str(i) + ',' + str(j)\n",
    "            if name in memo:\n",
    "                return memo[name]\n",
    "            memo[name] = matrix[i][j] + min(dp(matrix, i - 1, j - 1), dp(matrix, i - 1, j), dp(matrix, i - 1, j + 1))\n",
    "\n",
    "            return memo[name]\n",
    "        memo = {}\n",
    "        res = 10001\n",
    "        for k in range(len(matrix)):\n",
    "            res = min(res, dp(matrix, len(matrix) - 1, k))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        def dp(matrix, i, j):\n",
    "            if i < 0 or j < 0 or i > len(matrix) - 1 or j > len(matrix) - 1:\n",
    "                return 10001\n",
    "            if i == 0:\n",
    "                return matrix[i][j]\n",
    "            name = str(i) + ',' + str(j)\n",
    "            if name in memo:\n",
    "                return memo[name]\n",
    "            memo[name] = matrix[i][j] + min(dp(matrix, i - 1, j - 1), dp(matrix, i - 1, j), dp(matrix, i - 1, j + 1))\n",
    "\n",
    "            return memo[name]\n",
    "        memo = {}\n",
    "        res = 10001\n",
    "        for k in range(len(matrix)):\n",
    "            res = min(res, dp(matrix, len(matrix) - 1, k))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        # 备忘录法\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        memo = dict()\n",
    "        def dp(i, j):\n",
    "            if i == -1: return 0\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            # 状态: (i-1, j-1), (i-1, j), (i-1, j+1)\n",
    "            res = matrix[i][j] + min(dp(i-1, j-1) if j-1>=0 else 1e9, \\\n",
    "                               dp(i-1,j), \\\n",
    "                               dp(i-1, j+1) if j+1<col else 1e9)\n",
    "            memo[(i,j)] = res\n",
    "            return res\n",
    "        return min(dp(row-1, i) for i in range(col))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        memo = {}\n",
    "        r = len(matrix)\n",
    "        c = len(matrix[0])\n",
    "        for i in range(c):\n",
    "            memo[(0,i)] = matrix[0][i]\n",
    "        def dp(x,y):\n",
    "            if x < 0 or y < 0 or x >= r or y >= c:\n",
    "                return 10001\n",
    "            if (x,y) in memo:\n",
    "                return memo[(x,y)]\n",
    "            ans = min(dp(x-1,y-1), dp(x-1,y), dp(x-1,y+1)) + matrix[x][y]\n",
    "            memo[(x,y)] = ans\n",
    "            return ans\n",
    "        ans = min(dp(r-1,i) for i in range(c))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        #递归+记忆化\n",
    "        memo={}\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "        def dp(i,j):\n",
    "            #base case\n",
    "            \n",
    "            if i<0 or j<0 or i>=m or j>=n: return inf\n",
    "            if i==0: return matrix[0][j]\n",
    "            #memo剪枝\n",
    "            if (i,j) in memo.keys():return memo[(i,j)]\n",
    "\n",
    "\n",
    "            memo[(i,j)]= matrix[i][j]+min(dp(i-1,j),dp(i-1,j-1),dp(i-1,j+1))\n",
    "            return memo[(i,j)]\n",
    "        res=inf\n",
    "        for j in range(n):\n",
    "            res=min(res,dp(m-1,j))\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        cache = {}\n",
    "        def in_range(i,j):\n",
    "            return i >= 0 and i <= n and j>=0 and j < n\n",
    "        def dfs(i,j):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            key = (i,j)\n",
    "            if key in cache:\n",
    "                return cache[key]\n",
    "            tmp = []\n",
    "            for next_i,next_j in [(i+1,j-1),(i+1,j),(i+1,j+1)]:\n",
    "                if in_range(next_i,next_j):\n",
    "                    val = matrix[i][j] + dfs(next_i,next_j)\n",
    "                    tmp.append(val)\n",
    "            cache[key] = min(tmp)\n",
    "            return cache[key]\n",
    "        ret = []\n",
    "        for j in range(n):      \n",
    "            ret.append(dfs(0,j))\n",
    "        return min(ret)      \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,j):\n",
    "            if i == len(matrix)-1:\n",
    "                return matrix[i][j]\n",
    "            return min(dfs(x,y)+matrix[i][j] for x,y in [(i+1,j), (i+1,j-1), (i+1,j+1)] if 0<=y<len(matrix[0]))\n",
    "        res = 10000\n",
    "        for j in range(len(matrix[0])):\n",
    "            res = min(res, dfs(0,j))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "\n",
    "        #字典存储dp值\n",
    "        d = dict()\n",
    "\n",
    "        def dp(matrix, i, j):\n",
    "            #无效索引\n",
    "            if i < 0 or j < 0 or i >= m or j >= n:\n",
    "                return 99999\n",
    "            #base case:\n",
    "            if i == 0:\n",
    "                return matrix[i][j]\n",
    "            \n",
    "            #状态转移方程：\n",
    "            if d.get((i,j), 0):\n",
    "                return d[(i,j)]\n",
    "\n",
    "            d[(i, j)] = matrix[i][j] + min(\n",
    "                dp(matrix, i-1, j-1),\n",
    "                dp(matrix, i-1, j),\n",
    "                dp(matrix, i-1, j+1)\n",
    "                )\n",
    "            return d[(i, j)]\n",
    "        \n",
    "        res = 99999\n",
    "        for i in range(n):\n",
    "            res = min(res, dp(matrix, m-1, i))\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        ans = float(\"inf\")\n",
    "        table = {}\n",
    "\n",
    "        def dp(matrix, i, j):\n",
    "            if i < 0 or j < 0 or i >= n or j >= n:\n",
    "                return float(\"inf\")\n",
    "            if i == 0:\n",
    "                return matrix[0][j]\n",
    "            if f\"{i}-{j}\" in table:\n",
    "                return table[f\"{i}-{j}\"]\n",
    "            table[f\"{i}-{j}\"] = matrix[i][j] + min(\n",
    "                dp(matrix, i-1, j),\n",
    "                dp(matrix, i-1, j-1) if j > 0 else float(\"inf\"),\n",
    "                dp(matrix, i-1, j+1) if j < n-1 else float(\"inf\")\n",
    "            )\n",
    "            return table[f\"{i}-{j}\"]\n",
    "\n",
    "        for j in range(n):\n",
    "            ans = min(ans, dp(matrix, n-1, j))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "\n",
    "        def dp(matrix, i, j):\n",
    "            if i < 0 or j < 0 or i >= len(matrix) or j >= len(matrix[0]):\n",
    "                # 返回一个特殊值\n",
    "                return 99999\n",
    "            # base case\n",
    "            if i == 0:\n",
    "                return matrix[i][j]\n",
    "            if (i,j) in memo:\n",
    "                return memo[(i,j)];\n",
    "            # 状态转移\n",
    "            memo[(i,j)] = matrix[i][j] + min(\n",
    "                dp(matrix, i - 1, j), \n",
    "                dp(matrix, i - 1, j - 1),\n",
    "                dp(matrix, i - 1, j + 1)\n",
    "            )\n",
    "            return memo[(i,j)]\n",
    "\n",
    "        n = len(matrix)\n",
    "        res = float('inf')\n",
    "        # 备忘录里的值初始化为 66666\n",
    "        memo = {}\n",
    "\n",
    "        # 终点可能在 matrix[n-1] 的任意一列\n",
    "        for j in range(n):\n",
    "            res = min(res, dp(matrix, n - 1, j))\n",
    "        return res\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n=len(matrix)\n",
    "        m=len(matrix[0])\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if j<0 or j>=m:\n",
    "                return inf\n",
    "            if i>=n:\n",
    "                return 0\n",
    "            return min(dfs(i+1,j),dfs(i+1,j-1),dfs(i+1,j+1))+matrix[i][j]\n",
    "        return min(dfs(0,i) for i in range(m))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        def out_bounds(i: int, j: int) -> bool:\n",
    "            return not (0 <= i < m and 0 <= j < n)\n",
    "\n",
    "        @cache\n",
    "        def f(i: int, j: int):\n",
    "            if out_bounds(i, j):\n",
    "                return inf\n",
    "            if i == m - 1:\n",
    "                return matrix[i][j]\n",
    "            return matrix[i][j] + min(f(i + 1, j), f(i + 1, j - 1), f(i + 1, j + 1))\n",
    "\n",
    "        return min(f(0, j) for j in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n=len(matrix)\n",
    "        m=len(matrix[0])\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if j<0 or j>=m:\n",
    "                return inf\n",
    "            if i>=n:\n",
    "                return 0\n",
    "            return min(dfs(i+1,j),dfs(i+1,j-1),dfs(i+1,j+1))+matrix[i][j]\n",
    "        return min(dfs(0,i) for i in range(m))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        # for idx in range(1,n):\n",
    "        #     matrix[idx][0] += min(matrix[idx-1][0],matrix[idx-1][1])\n",
    "        #     matrix[idx][n-1] += min(matrix[idx-1][n-2],matrix[idx-1][n-1])\n",
    "        #     for jdx in range(1,n-1):\n",
    "        #         matrix[idx][jdx] += min(min(matrix[idx-1][jdx-1],matrix[idx-1][jdx]),matrix[idx-1][jdx+1])\n",
    "        # return min(matrix[n-1])\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            return matrix[i][j] + min(dfs(i+1,j+d) for d in [-1,0,1] if 0 <= j+d < n)\n",
    "        return min(dfs(0,j) for j in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if j < 0 or j >= n:\n",
    "                return inf\n",
    "            if i == m:\n",
    "                return 0\n",
    "\n",
    "            return min(dfs(i + 1, j), dfs(i + 1, j - 1), dfs(i + 1, j + 1)) + matrix[i][j]\n",
    "        return min(dfs(0, j) for j in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j): # 到达[i,j]的最小下降路径\n",
    "            if i == 0: return matrix[i][j]\n",
    "            x = matrix[i][j]\n",
    "            return min(dfs(i - 1, nj) + x for nj in (max(0, j - 1), j, min(n - 1, j + 1)))\n",
    "        return min(dfs(m - 1, j) for j in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        memo={}\n",
    "        row, col = len(matrix), len(matrix[0])\n",
    "        def dp(i, j):\n",
    "            # 以matrix[i][j]结尾的最小路径和\n",
    "            # 越界\n",
    "            if not (0<=i<row and 0<=j<col):\n",
    "                return 10001\n",
    "            if i==0:\n",
    "                return matrix[i][j]\n",
    "              \n",
    "            if (i,j) in memo:\n",
    "                return memo[(i,j)]\n",
    "            res = matrix[i][j]+min(\n",
    "                dp(i-1, j-1),\n",
    "                dp(i-1, j),\n",
    "                dp(i-1, j+1)\n",
    "            )\n",
    "            memo[(i,j)]=res\n",
    "            return res\n",
    "        minsum = 1000001\n",
    "        for j in range(row):\n",
    "            minsum = min(dp(col-1, j), minsum)\n",
    "        return minsum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == row - 1: return matrix[i][j]\n",
    "\n",
    "            minValue = float('inf')\n",
    "            for index in range(-1, 2):\n",
    "                # print(index)\n",
    "                nextJ = j + index\n",
    "                if nextJ < 0 or nextJ >= col: continue\n",
    "                minValue = min(minValue, dfs(i + 1, j + index))\n",
    "            \n",
    "            return minValue + matrix[i][j]\n",
    "        \n",
    "        minValue = float('inf')\n",
    "        for index in range(col):\n",
    "            minValue = min(minValue, dfs(0,  index))\n",
    "        return minValue\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i == m-1:\n",
    "                return matrix[i][j]\n",
    "            return min(dfs(i+1, x) for x in [j-1,j,j+1] if 0<=x<n) +matrix[i][j]\n",
    "        \n",
    "        return min(dfs(0, j) for j in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        row, col = len(matrix), len(matrix[0])\n",
    "        dp = {}\n",
    "\n",
    "        @cache\n",
    "        def min_path(cur_row, cur_col):\n",
    "            if (cur_row, cur_col) in dp:\n",
    "                return dp[(cur_row, cur_col)]\n",
    "       \n",
    "            if cur_col < 0 or cur_col >= col:\n",
    "                return inf\n",
    "            if cur_row == row - 1:\n",
    "                return  matrix[cur_row][cur_col]\n",
    "            \n",
    "            cur_value = matrix[cur_row][cur_col]\n",
    "\n",
    "            return  cur_value + min([min_path( cur_row+1, next_col) for next_col in [cur_col-1,cur_col,cur_col+1]])\n",
    "        candidates = [min_path(0, c) for c in range(col)]\n",
    "        return min(candidates) \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y):\n",
    "            if x == n - 1:\n",
    "                return matrix[x][y]\n",
    "            ret = inf\n",
    "            for dx, dy in [[1, -1], [1, 0], [1, 1]]:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < n and 0 <= ny < m:\n",
    "                    ret = min(ret, dfs(nx, ny) + matrix[x][y])\n",
    "            return ret\n",
    "        return min(dfs(0, i) for i in range(m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        rows = len(matrix)\n",
    "        cols = len(matrix[0])\n",
    "        # dp = [[0]*(cols+1) for i in range(rows+1)]\n",
    "        # for row in range(1,rows+1):\n",
    "        #     for col in range(1,cols+1):\n",
    "        #         if col == cols:\n",
    "        #             dp[row][col] = min(dp[row-1][col],dp[row-1][col-1]) + matrix[row-1][col-1]\n",
    "        #         elif col == 1:\n",
    "        #             dp[row][col] = min(dp[row-1][col],dp[row-1][col+1]) + matrix[row-1][col-1]\n",
    "        #         else:\n",
    "        #             dp[row][col] = min(dp[row-1][col],dp[row-1][col-1],dp[row-1][col+1]) + matrix[row-1][col-1]\n",
    "        res = float(\"inf\")\n",
    "        # for col in range(1,cols+1):\n",
    "        #     res = min(res,dp[rows][col])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(row,col,rows,cols):\n",
    "\n",
    "            if row < 0 or row >= rows or col < 0 or col >= cols:\n",
    "                return float(\"inf\")\n",
    "\n",
    "            if row == rows - 1:\n",
    "                return matrix[row][col]\n",
    "\n",
    "            res = min(dfs(row+1,col-1,rows,cols),dfs(row+1,col,rows,cols),dfs(row+1,col+1,rows,cols)) + matrix[row][col]\n",
    "            \n",
    "            return res\n",
    "\n",
    "        for col in range(cols):\n",
    "            res = min(res,dfs(0,col,rows,cols))\n",
    "\n",
    "        return res\n",
    "        # return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def dfs(x, y):\n",
    "            if x == 0:\n",
    "                return matrix[x][y]\n",
    "            cur = [dfs(x-1, y)]\n",
    "            if y > 0:\n",
    "                cur.append(dfs(x-1, y-1))\n",
    "            if y < n - 1:\n",
    "                cur.append(dfs(x-1, y+1))\n",
    "            return matrix[x][y] + min(cur)\n",
    "\n",
    "        n = len(matrix)\n",
    "        #print (list(dfs(n - 1, i) for i in range(n)))\n",
    "        return min(dfs(n - 1, i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, a: List[List[int]]) -> int:\n",
    "        n = len(a)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == n - 1: return a[i][j]\n",
    "            return a[i][j] + min(dfs(i + 1, nj) for nj in range(j - 1, j + 2) if 0 <= nj < n)\n",
    "        return min(dfs(0, j) for j in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        dic = {}\n",
    "        def dp(col, level):                \n",
    "            if col < 0 or col >= len(matrix):\n",
    "                return float('inf')\n",
    "            if level == 0:\n",
    "                return matrix[level][col]\n",
    "            key = str(col) + '-' + str(level)\n",
    "            if key in dic:\n",
    "                return dic[key]\n",
    "            add = min(dp(col-1, level-1),\n",
    "                       dp(col, level-1),\n",
    "                       dp(col+1, level-1))\n",
    "            res = matrix[level][col] + add\n",
    "            dic[key] = res\n",
    "            return res\n",
    "        return min(dp(i, n-1) for i in range(len(matrix)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        ans = inf \n",
    "        n = len(matrix)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i >= n - 1:\n",
    "                return 0\n",
    "\n",
    "            tmp = [(i + 1, j - 1), (i + 1, j), (i + 1, j + 1)]\n",
    "            return min(matrix[x][y] + dfs(x, y) for x, y in tmp if 0 <= y < n)\n",
    "\n",
    "        return min(matrix[0][x] + dfs(0, x) for x in range(n))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        memo = {}\n",
    "        def dp(matrix, i, j):\n",
    "            if i < 0 or j < 0 or i >= len(matrix) or j >= len(matrix[0]):\n",
    "                return 99999\n",
    "            if i == 0:\n",
    "                return matrix[i][j]\n",
    "            \n",
    "            # r = min(dp(matrix, i-1, j-1),dp(matrix, i-1, j),dp(matrix, i-1,j+1)) + matrix[i][j]\n",
    "            if '{}-{}'.format(i,j) not in memo:\n",
    "                r = min(dp(matrix, i-1, j-1),dp(matrix, i-1, j),dp(matrix, i-1,j+1)) + matrix[i][j]\n",
    "                memo['{}-{}'.format(i,j)] = r\n",
    "                return r\n",
    "            else:\n",
    "                return memo['{}-{}'.format(i,j)]\n",
    "        r = []\n",
    "        res= float('INF')\n",
    "\n",
    "\n",
    "\n",
    "        for col in range(n):\n",
    "            rr = dp(matrix, n-1, col)\n",
    "            r.append(rr)\n",
    "            # res = min(res, dp(matrix, n-1, col))\n",
    "        return min(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        # n = len(matrix)\n",
    "        # dp = [[0] * n for _ in range(n)]\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         if i == 0:\n",
    "        #             dp[i][j] = matrix[i][j]\n",
    "        #             continue \n",
    "        #         l = inf if j-1 < 0 else dp[i-1][j-1]\n",
    "        #         u = dp[i-1][j]\n",
    "        #         r = inf if j+1 >= n else dp[i-1][j+1]\n",
    "        #         dp[i][j] = min(l, u, r) + matrix[i][j]\n",
    "        # return min(dp[-1])\n",
    "\n",
    "        ##################\n",
    "        @cache\n",
    "        def down(i, j):\n",
    "            nonlocal n\n",
    "            if j < 0 or j >= n:\n",
    "                return inf \n",
    "            if i == 0:\n",
    "                return matrix[i][j]\n",
    "            res = inf \n",
    "            for k in [-1, 0, 1]:\n",
    "                res = min(res, down(i-1, j+k))\n",
    "            return res + matrix[i][j]\n",
    "        \n",
    "        n = len(matrix)\n",
    "        res = inf\n",
    "        for i in range(n):\n",
    "            res = min(res, down(n-1, i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        @cache\n",
    "        def f(x,y):\n",
    "            if x==m:\n",
    "                return 0\n",
    "            ret=10**7+7\n",
    "            for dy in (-1,0,1):\n",
    "                if 0<=y+dy<n:\n",
    "                    ret=min(f(x+1,y+dy),ret)\n",
    "            return ret+matrix[x][y]\n",
    "        \n",
    "        ans=10**7+7\n",
    "        for col in range(n):\n",
    "            ans=min(ans,f(0,col))\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i==m-1:\n",
    "                return matrix[i][j]\n",
    "            num=matrix[i][j]\n",
    "            if i+1<m and j==0:\n",
    "                num+=min(dfs(i+1,j),dfs(i+1,j+1))\n",
    "            elif i+1<m and j==n-1:\n",
    "                num+=min(dfs(i+1,j),dfs(i+1,j-1))\n",
    "            else:\n",
    "                num+=min(dfs(i+1,j),dfs(i+1,j-1),dfs(i+1,j+1))\n",
    "            return num\n",
    "        res=float('inf')\n",
    "        for j in range(0,n):\n",
    "            res=min(res,dfs(0,j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFallingPathSum(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == n - 1: return matrix[i][j]\n",
    "            ans = inf\n",
    "            for x, y in (i + 1, j - 1), (i + 1, j), (i + 1, j + 1):\n",
    "                if 0 <= x < n and 0 <= y < n:\n",
    "                    ans = min(ans, dfs(x, y) + matrix[i][j])\n",
    "            return ans\n",
    "        ans = inf\n",
    "        for j in range(n):\n",
    "            ans = min(ans, dfs(0, j))\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
